If it is a folder you created, though... it is you that has to set the permissions - not the hosting company... yes, they were right in saying that the permissions from their end are correct. But if you create a folder and upload it to your root on the hosting server, you then need to set the permission after upload. Many FTP programs can do this where you would create a CHMOD command to give it permissions like 0777 (this is assuming your on a Linux server. Windows severs are different.)... that would allow write access to the folder form your scripts.
Cheers,
Brian