OK I've done a bit of research in the last few days as I also came from Palm OS and loved my Resco backup software (Fully automated backup of everything in the phone, except bluetooth settings).
So.. facts as I've found them (Feel free to correct me and site source/app):
1) NOTHING will backup android today like the old Palm OS. That means even with the best backup software out there will require the user to do some re-engineering should they wipe/restore a phone.
2) Most of the better backups require ROOT access since many of the SYSTEM settings are protected. Root Grants that ability to backup the system settings. Contacts, App APKs (install files), and other basic data do not require root.
3) No app out there today can backup every apps settings!!! (This is my biggest concern). Some of them, like MyBackupPro have worked with developers to allow the backup software to get to the settings, but the vast majority of apps out there have no such partnership. Those that do often partner with one of the backup solutions and not all... so it's really not that useful just yet.
Per MyBackupPro site:
"FAQ 4) Can MyBackup backup the data specific to my other applications?
We can not get the applications data because of security built into Android. But we have provided developers the ability to integrate with us and some are beginning to do this. If you would like any application to have the ability to be backed up by MyBackup Pro, you may want to contact the developers of such applications and have them contact us for instructions on how to integrate with us."
So what does this all mean... basically we are somewhat out of luck at the moment.
My personal preference currently is as follows:
1) Allow Gmail to backup Contacts normally as part of it's Sync
2) Use AppBrain to remember which apps I've installed to allow for easy replacement.
3) Use ASTROFile Manager to provide backup of the APKs to the SD card in case I cannot get to Appbrain for some reason (I don't like cloud backup solutions personally)
That's it... I figure for now, if I'm going to have to go in for each app and re-do settings, then it's really not much extra work to change phone settings.
I also contacted Resco software, the people who made RescoBackup for Palm, and they replied saying they were working on some Android Apps but had no release dates nor further information at this time. (*Crossing my fingers for an early Xmas gift*)
Anyway if anyone finds out any further info, please share it... and if you 'claim' that your backup works for app settings, please wipe your phone and restore it first, before posting without testing.. I've gone through a lot of headache buying/refunding apps based on peoples unfounded posts.