Hah I actually signed up for jungle disk after this happened.

I like it so far but I don't think it solves the alias/hardlink problem, so you'd just get one or two good snapshots before it got to be really expensive. The great feature of time machine (or rsync --link-dest) is that your snapshots share storage of unchanged files, and I don't know how to make S3 do that.