I've just done the same, if you can still turn your old phone on then
backup Cardio Trainer to your SD card and then swap it back to the new
phone and go to Restore (hit Menu when on the History page) this will
copy all the data to your new phone :D
If you have used the same Google account to setup your new phone you
should be able to go to the Android Market and go to the Download tab
to download all your Paid Apps? Worked ok for me?