Ahh, I'd forgotten that, still having trouble though (and the example is still wrong!)
The post now looks like:
POST http://.../api.ashx/v2/users/16031/avatar.xml HTTP/1.1
Content-Type: multipart/form-data; boundary=0131befff9914a39a2391fb0ac3381c9
Content-Disposition: form-data; name="UserId"
Content-Disposition: form-data; name="AvatarData"; filename="3794-logo.png"
Without the Put header I get 404, with the Put header I get "Please provide either AvatarUrl or AvatarData"
Any ideas? I've used this method to successfully upload Media posts and attachments before, so I don't think thats it?