I made the Mozy to Backblaze jump a few days after Mozy thanked me for being an early adopter by quintupling my bill. I only had about 250GB to back up, computer was on 24 hours, I throttled it a bit during evening hours to not interfere with Netflix, and it was about three weeks to finish the backup. I don't know if they have a graduated scale if you have to back up a lot more.
So far, I'm very happy, but I haven't had to restore yet...