I wouldn't want to be in your shoes, the migration from magento 1.3 to anything higher seems to be a trifle hard, from what I read on the bulletin boards.
Why don't you migrate directly to 1.7 ?
I've migrated from 1.5 to now running Magento 1.7 and will migrate to 1.8 sometime this year. I always wait a bit to upgrade so that I know the new release is stable, but preferably I'm never more than one version behind.
You could try to use something like cart2cart ? They offer an automated solution to migrate your shop.
Here are some useful links :
http://www.shopping-cart-migration....tion-by-version/9144-magento-13-to-magento-17
www.crucialwebhost.com Magento Services
http://www.magentocommerce.com/boards/viewthread/302770/