I have added products but when I try to upload images I get the following message:
Unable to create directory '/home/mystore/public_html/media/tmp/catalog/product'.
I checked the folder permissions and it is 777.
Can anyone advise on where I am going wrong please.
First thing to check would be your PHP version.
Make sure your hosting server is running the latest stable version of PHP, I've previously experienced folder write errors with outdated PHP versions.
According to the Magento system requirements page (http://magento.com/resources/system-requirements) 5.4 is suitable to run Magento.
But i would ask your hosting provider to update you to the latest stable version just to rule this possibility out.
Additional things to check.
Make sure that your permissions are set RECURSIVE to 777 for your Media and VAR folder. Setting these permissions recursive is extremely important and will not work without.
Rename your .htaccess that is in the media folder, attempt the upload (your htaccess may be causing issues with the upload)
If these fail it could well be to do with your PHP build. But we will explore this possibility later.
To correct some misinformation, the PHP version itself has nothing to do with directory writing.
As for the file permissions, it can be a little misleading as different servers have different requirements.
If the server is running SuPHP / SuExec, all files should be set to 644 and all directories to 755. Otherwise only some files should be set to 644/755 while others should be set to 666/777 as per Magento's official documentation.
If you are not sure whether your server is running SuPHP / SuExec, it is better to confirm that with your hosting provider first and adjust the file permissions accordingly.