Whilst it makes a lot of sense to make a "fresh start" when you want to upgrade or migrate your Magento store to a new version and theme you may well be underestimating the work involved to rebuild your catalog exactly as it was in the old store.
Unless you go to a company that specialises in Magento data migration you will need to consider carefully how you will migrate all your products data (and images), categories and CMS pages.
There are various tools available to help you export your product and category data including the inbuilt Magento export tools.
For product data I would export using Magento and then either try a reimport to the new version, or import into Excel where you can make any changes you require and use something like MAGMI to do the import. This will depend a lot on the product types you have. Even after a basic import you may still need to do a lot of manual editing of each product.
The same applies with categories, my experience has shown that even if you can reimport the category data you will need to still do a lot of manual editing to restore the structure that you had before.
With CMS its a bit easier as it is fairly easy to simply dump the CMS tables from your database and then import them back into SQL, this has worked well for me in the past.
If your shop is large and an upgrade is out of the question (and if you have the budget) get a quote from one of the companies that specialises in Magento data migration.
If that is not an option, have a look at what you can achieve with the import export tools that are around.
I would also recommend experimenting with the upgrade, it will save you a lot of work!
