Enabling versioning on your bucket is the right solution. It can be used to protect both against accidental deletes and overwrites as well.
There's a question on the S3 FAQ, under "Data Protection", that discusses exactly this issue (accidental deletes/overwrites): http://aws.amazon.com/s3/faqs/#Why_should_I_use_Versioning