Change the permissions on the wp-content directory to 766. If you still have problems, try 767 or 777. Once your uploads are working, change the permissions on wp-content back to 755 again and check that everything still works OK.
kylepoyser,
To add a little more to esmi’s instructions. Changing permissions is generally done by using an FTP program such as Transmit. Right click on a folder/image/etc and select ‘Get Info’.