How much upload bandwidth do you have? You might need a solution where you can seed the first backup at the provider's datacenter (which means a local company makes sense) and then do smaller incrementals thereafter over your line. I use Livevault and just seeded the initial bulk