Posted this earlier on another thread, but maybe it could help you as well. At least it worked for me.
First of also checked everything...double. The permissions, paths, versions, updates, themes, I cleared caches...you name it. I've temporarily disabled other plugins, but nothing seemed to work and the upload error remained.
Then finally, my last resort, I've changed a setting in permalinks. It was originally on a default setting and I've changed it to the second one. I've got the Dutch version and there it's called (translated)"year, month, day and name". That did it. The problem was solved.