Hmmm... If you can check owner info that might provide a clue too. Another thing you can check is to do something like this:
1) logged in via FTP (or whatever)
2) manually create a file in that directory and check what permissions are auto assigned. If they are different (like 765 or 766) you might try those. Obviously 777 would work, but not a good idea.
It sounds like maybe apache (or whatever web server... is this IIS???) is running under a different account than WordPress (PHP)... Sometimes this mismatch in owner between the context WordPress is running in verses what the file system will honor as the "owner" of that folder via the 755 permissions prevents WordPress (PHP) from writing to the particular location.
Hope that helps. At the very least it should provide more info if you do have to talk to the host. Sometimes they isolate PHP and apache (or whatever web server) processes under different accounts and so there can by symptoms like this, especially in some shared hosting environments.