While you do say that you have checked permissions, that's still where I would start, as I've had this issue myself, frequently, and it's nearly always been a permissions problem.
First of all, go to admin/config/media/file-system, and click "Save configuration". This will cause Drupal to re-evaluate the permissions of the set directories, and will give you error messages if it finds a problem.
Second: I assume that you have a apache, or www-data, or other users, that owns the webserver, as opposed to the php user? On a Linux or Mac system, sudo to that user. Trying to write a file as the right user, is the best way to truly ensure that you have the right permissions. Go to sites/domain.com/files/, and call "echo data > new_file; cat new_file;" in a terminal. This will verify that you actually can write to the write directory. Do the same with your tmp dir. Hopefully someone else can suggest how to perform the same actions on a system like windows.
Third: To rule out directory permissions, recursively apply 777 the the files directory. You can restore more sane permissions afterwards with
find . -type d -print0 | xargs -0 chmod 755
find . -type f -print0 | xargs -0 chmod 644
Fourth: Ensure that the tmp directory that has full permssions.
Fifth: You may need to start debugging the code if you have figured it out by now.