I tried Carbonite several years ago and found it quite lacking. I did not dig into as much detail as Narog2000 but came to similar conclusions.

I used to be a happy Mozy user. However, about a year ago, they suddenly doubled their price and put a soft cap (with fairly pricey per gb over that) on the amount you could backup (they used to be unlimited) with no increase in quality, support, or service.

Right now, I'm evaluating Crashplan (so far they seem pretty good but with periods of slow upload speed). I've also heard good things about Backblaze, iBackup (or was it iDrive?), and LiveDrive but I haven't evaluated any of them.