delete S3 object

Does your keys have an http://... prefix?

My guess is that you are mistakenly passing a URL instead of a key. Your request should probably look more like this:

client.DeleteObject(new Amazon.S3.Model.DeleteObjectRequest() { BucketName = "xxxx", Key = "filename"});