Contacts, email, and calendar are synchronized with the "cloud". I use Astro File explorer to backup my apps, and AppBrain to sychronize my apps with the Android market. Your paid apps will be available for download on your new device, as long as you use the same Google account.
If you use a free program like Evernote, it also has online synchronization. The program you mentioned (Note Everything) has a backup option in the full version. Astrid Tasks sychronizes to Google Tasks, and also has a SD card backup. ADW Launcher has a backup option for your home screen layout as well as ADW settings. Basically, your apps may have backup options in them.
Combined, all these programs provide me with all the backup that I need.
Other backup apps like "My Backup Pro" may not provide you with additional functionality than what you need, already have, or can find for free. For example, do you need to restore text messages? Personally, I have no purpose for keeping old text messages, so I would not spend $5 to back them up.
Sprint S.M.A.R.T Agents Sprint S.M.A.R.T Agent are here to help Monday through Sunday 6:00 AM CT - 6:00 PM CT. If you need to speak to an agent outside of these hours, please visit Sprint Chat