This is a fast changing market. Use of Amazon's S3 service is interesting - through a few intermediaries, ElephantDrive is also an unknown, who knows when google will come out, so whilst carbonite looks very very interesting, I'm just not happy to commit to a year up front.
Also here in the UK BT (telco) have just launched their service - a little more pricey, but 20Gb of storage + backup sw comes in at 4.99 UKP which is probably just fine for me -- see
http://www.btdigitalvault.bt.com/