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
The only experience I've had with the uploader not working was mysteriously to do with the base URL domain not matching either the link, skin, media or javascript URL domain as specified in System > Configuration > Web.
I didn't investigate further, it is probably something to do with cookie origin policies which you cannot do much about. All you can do is check they all match for at least the default config, individual stores won't affect the admin URLs.