The uploads folder and its contents, including subfolders and images, needs 755 permissions, not 777.
755 means the owner (usually www-data or whatever you named your webserver’s owner) has read/write/execute permissions. Everyone else has read/execute permissions. The search engines do not need to be able to write to your webserver to index it.
I’ve also seen the 777 recommendations. It appears there is a misconception about the difference between the owner and the permissions. If the file/folder’s owner is the same user as the webserver, you can edit, write, and delete to the files from within WordPress without giving the world write access to your website.
For example, on a linux server, you can login via ssh and type
cd \var\www\sitename\wp-content
ls -l
A list of all files and folders within wp-content appears along with their owners. Under this list, look at the folder owners and verify they are all the same as your webserver. For example, www-data. If not, chown the entire directory to change the owner.
chown -R www-data:www-data uploads
The permissions remain set to 755, not 777, and uploads/theme editing now works.
On my sites, owner mixups normally happen when I untar/unzip a file into my home directory and move it to my uploads directory.
In your case, your problem might be in .htaccess. Check it for rewrite rules for .gif, .png, and .jpg.
Google webmaster tools is a freebie, and it’s good for checking what Google’s crawlers can access. Webmaster’s error messages (or lack thereof) may give you more insight into what’s going on. I understand it helps if your xmlsitemap includes images, but I don’t know for certain because I’ve always included images in mine.
Google also has images best practices that you may want to review.
