If you don't mind the additional cost, you can physically send Amazon a harddrive: http://aws.amazon.com/importexport/

nothing says "cloud" like sending a physical hard drive through the mail.

"Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway. —Tanenbaum, Andrew S." - http://en.wikipedia.org/wiki/Sneakernet

There's also Amazon Direct Connection (http://aws.amazon.com/directconnect/) if you happen to be on the same backbone / data center.

But then you can do incremental backups which should be faster. Although I admit I am not sure how to do it with encryption (impossible?).

That's what duplicity is for: http://duplicity.nongnu.org/

It uses rsync's algorithm to figure out what has changed, and everything is encrypted locally.

(The site says it's in beta, but it's said that for years.)

Makes me wonder what Amazon is doing to commoditize its complements, i.e. what it's doing to improve high speed internet access. There are a lot of people in my vicinity who have no option faster than a wireless 3Mbps connection capped at a few GB per day. And this is within easy distance of Amazon's East Coast data center.

Amazon should be big fans of Google Fiber. With a gigabit this stuff is a lot more impactful.