Problems with Batch add files and uploading photos

[dimples]

I have just had to change my web hosting company and am now having problems at the Batch Add Files stage. It is showing the warning "the script can't write in this directory, you need to change it's mode to 755 or 777 before trying to add these files" 
I have read all the instructions on here about this and my new host company www.bigwetfish.co.uk have checked and told me how to check that the public_html/gallery/album files are all pointing to 755.
Please can you help me? Many thanks.

[Nibbler]

755 might not be appropriate (as the message suggests). Have you tried 777?

[Joachim Müller]

Documentation: setting permissions