I ran into this problem this week.  I made a folder, set my permissions, and was stumped to find I couldn’t upload my files.  I found through some trial and error that this only applied to PDFs as other people were uploading their images just fine.  Equally as confusing, I could indeed still upload PDFs as a Super Admin.  So I was convinced Expression Engine was broken in regards to member permissions.

But with some research on the new EE2 settings, I found out how to fix this.  (note, it’s a bit of a workaround, but hey, it works)

In the control panel: Admin -> Security and Privacy -> Security and Sessions
Set “Apply XSS Filtering to uploaded files?” to “No”

When the EE2 came out, the XSS security settings was added to help when pdf files appear to have problems. If you trust your uploaders, turning it off should be okay.  People in forums are starting to realize that those XSS security settings may be a bit too strict to actually be useful.
(Of course, you should first make sure that folder has permissions for your user group, that might be your solution on its own.)