Martin,
Nine times out of ten, these problems are usually something simple... so I will start with simple. Did you remember to set the permissions of the folder once it was created?
If you are creating the folders manually and uploading the folders, you will need to chmod them to something like 0777 so they will have read and write capabilities. If you are allowing the folders to be created on the fly, then the parent folder will have to be assigned the recursive permissions of 0777 so that you can write within the folder and into all the child folders.
Cheers,
Brian