We have crated a subsite for one of our clients, who has Contribute permissions
for the site.

He can upload documents. However, when he tries to delete a document WSS says,
"Error: Access denied."

Does anyone know why this is?

According to the permissions page,
Contribute - Can view, add, update, and delete