Ok - Strange - I changed the permissions to 777 yesterday and it still didn't work.
I've double checked them today and they've reverted to 755! I changed them to 777 now and it's spot on!
Thanks for your help, Phil!
Whoop!
If you might be able to shed some light on how to remember what the customer has written, if they get the captcha wrong, that would be fantastic!