I don't know about Titanium Backup or My Backup, but using Astro to back up your apps only works halfway.
If you restore from the Astro backup, the apps are there, but the Android Market doesn't know it, so you won't get any updates. When you re-install them, from the Market, you will get a warning you are re-installing them even though it doesn't recognize that it was ever installed in the first place.
This is a problem with paid programs, since you will never get any updates and you may or may not be able to use them. I paid for 2 programs before I changed from a Droid to the HTC Incredible. iReader worked, but doesn't show up as being installed. Documents To Go didn't work and took 1/2 hour on the phone with them to get it to work. Even after it was fixed, it still doesn't show up as being installed, so I will never get any updates for Documents To Go.
A tip with Documents To Go: call the sales department, not the technical support department. The technical support people will completely ignore this problem. Also, you need them to do 2 things: the first is to associate your unlock key with your new registration key. The second is that they have to make a change in their system that you have a "direct" version. Just associating the unlock key with the new registration number by itself doesn't work because the Market doesn't recognize that you've downloaded the program and Documents To Go unlocks through a Market process.
The Market does show that I've purchased iReader, but it's not installed and the Market will not prompt you to re-install the apps that it knows you've already purchased if you switch phones.