What open source tools are you using to backup to S3 from linux? I imagine the good ones will add in support for S3 versioning.
Another is the Boto Python library (more or less a wrapper for all AWS stuff). http://code.google.com/p/boto/
Hopefully both of these will get version control support real soon.