I can upload the avatar onto my site. Have you had your host check your server settings? Perhaps they are blocking you from doing this.
We're into that element of chasing it down now. I'm sure it's something I installed but with the added surprise of uploading using IP working and failing using the name - it's a little weird...
I've logged into several and uploaded it perfectly..