I have and use MyBackup Pro from the Market (the full, paid version of MyBackup).
It works. Backs up apps (paid and free) and settings (contacts, SMS, email, etc.), you can choose which things to back up, you can backup to the SD card or to their website.
For paid apps, they're tied to the Google account you used to buy them. So, if you are joesmith at gmail dot com on your current phone, you use that same account on your new phone (doesn't matter which Android phone it is), and your paid apps will show up under "downloads" in the Market. It may take time for them to all show up (a few folks have reported it taking up to a day).
When I went from the Hero to the EVO, all of my paid apps were there immediately. None of my free apps showed up though. Not sure why that was.
However, since I was going from the Hero (running 1.6) to EVO (running 2.2), I didn't re-install them from my backup. Instead, I opened the backup to see which ones I'd had then downloaded them again from the Market. (No reason for doing it that way. It just seemed cleaner to me.)