Some of what you're describing that you want backed up to have a turn key solution for in the event of a phone replacement lives in privileged areas so you need to be rooted to backup and restore it. MyBackup Pro has a companion product called MyBackup Root, and there's also Titanium Backup and nandroid image backups, all for root users only.
BTW, I personally recommend backing up your phone storage to your pc, and if you want to put it on the cloud as well, great.
Full phone backups can run in to the gigabyte range (a full image of just my phone is close to 2 GB right now), so while cloud backups that size are possible, local storage (pc) will be faster and easier.
Hope this helps!
PS - just speaking for myself, between my internal and external sd cards, I have 70 GB of storage. That's a lot for a cloud service but possible I suppose. I think that cloud services are great but maybe not the only way to look at the problem.