[Newbie]Cannot Upload Themes/Pictures

So what is the current permissions of those folders they refered to now?

HelloShay,

Try 777 for /uploads/. 775 should not work for php-cli, and may be will not work for php-cgi. So if you set 777 and you’ll got the same or 500 error, try to set 755.

Try changing the permissions on the wp-content directory to 766. If you still have problems, try 767, 775 or 777. Once your uploads are working, change the permissions on wp-content back to 755 again and check that everything still works OK.
http://codex.wordpress.org/Changing_File_Permissions