I don't think backing up large quantities of data into the cloud is a viable option yet, no matter how cheap. Downloads have become fast enough to suggest it might be, however, the problem is upload. Every ISP here is basically the same, they advertise insane download rates, but uploading takes a holy eternity. I wouldn't even dream of backing up 40 GB into the cloud. A LAN however can give you a gigabit bandwidth.
I'm with Tao here, for me, backing up means a NAS w/ RAID system - out of the box solutions have become affordable, and a basic RAID can even be built out of an old NIX box for free. Invest a little in the hard drives (big, but not too big, and quality stuff) and set it up so it mirrors at the very least (most basic and cheapest solution). RAID allows you to do crazy stuff (one disk for checksums only and so on), which is basically more than you'd ever need. You don't want to build a high performance I/O system with lots of traffic and load, which makes technical failures more likely over time, but a backup service. If you can recover one crashed disk from the others, it should suffice.
2nd, very important thing - off site backup. What if your house burns down? Less likely than an HD head crash, but still not impossible. That is the tricky part. I don't have a solution for me for that yet.