Why I'm getting error on Avatar uploads

For some reason I am getting this error when trying to upload Avatars from the user UI:
http://screencast.com/t/OTk1MjUyOT

The read/write positions are 777 for the entire folder, I've checked to make sure the settings allow for avatar uploads, but now I've run out of things to check.

Any ideas?