An error occurred in the upload. Please try again later

I have a TinyMCE editor on the front end of my site so users can add posts. Everything is working perfectly except that the file uploader (the new one, in 3.5) is not letting anyone upload files. It just gives the error “An error occurred in the upload. Please try again later.”

But, it’s only spitting out the error for non-admins. If I’m logged in as an admin, I can upload image just fine from the front-end.

I have tried disabling all plugins. No help. I am using a modified twenty eleven theme. Still doesn’t work.

It seems like it’s a user-permission-based problem, but I don’t know what user-permission (besides upload-files) would help me here.

Any help would be awesome. Is this a bug in 3.5 or something? I’ve seen many people with variations of this problem since the update but no solution that works for me.