You are correct, it will take an incredible amount of time to perform the initial backup. Upload speeds really are pretty terrible all over North America, so you kind of get screwed there.

It took me about a week to back up all my data, and that was with 5Mbps up. But the whole idea is that after that, it's only a little each time you add/change files.

Also - and I don't know how/if Carbonite does this - but with Mozy you can set/schedule upload speeds and set upload times. And if the upload is ever interrupted, the program will just pick up where it left off. It's really set-it and forget-it.

But I do understand that you don't have the biggest outbound pipe, so that would be a concern.