All the permissions are correct and the php.ini is fixed, and there's no problem with SSL or secure admin interface but it still won't upload.
I click on a product, go to the Image section, select an image to upload and it appears to upload. However, the image doesn't appear in the list of product images and then I get kicked back out to the login page!
I was unable to get the built-in Flash uploader playing nicely with our production server, even though it worked fine in the development environment... but I replaced it with this extension and uploads work fine now: http://www.magentocommerce.com/magento-connect/Tobias+Renger/extension/1756/no-flash-uploader