As far as I understand he is using S3 as a dumb block-level store. He has implemented a file system on top of S3.
All customer data is stored in different files, it's just that those files don't map 1:1 to S3 objects.
The tarsnap client does the encryption. The server never sees plaintext. I think it's reasonable to consider the tarsnap protocol as adequate separation, since an error on the server wouldn't be able to leak customer data (except for stats about size and access patterns, perhaps, but that could happen regardless of how the data is chunked together).
They'd better.
I'm as surprised as you are (well, probably not because I'm not using S3, but I know a bit about how it is put together and I can't believe the Amazon people are happy about having this happen to them, it's the exact opposite of what should happen in a 'cloud' storage situation).
I think there will be some pretty high level meetings on this glitch, the one thing you don't want is customer data going absent-without-leave, even if only on a holiday instead of a permanent departure.
Isn't it against your instinct to have data from different customers live in what amounts to be the same file? I understand you've got it encrypted to the hilt but that seems 'un-Colinish' ;)