log in via ftp
delete the offending directory.
now recreate it (using ftp!)
it should work now
the problem is when you use mkdir(), the directory will not have the same uid as php, i beleive its created by the uid of the webserver. and w/ safemode on,
you cant write to a directory owned by the webserver
but if you need to dynamically create directories, i think you should get that script running as a cgi so you turn off safemode. talk to your host again and tell them it doesnt work.
there is a way to get around it though, but its messy. you would need to use phps built in ftp functions to log into your own site via ftp automatically w/ the script, and create the directory on the fly through ftp, THEN you can use the directory. this should work because then the directory would then inherit the the uid from the ftp user, and php could write to it. i did this once and it worked. i dont know if it will work for all servers though, i think it might depend on how it configured.
but ftp is slow, and having to wait for your script to initiate a bunch of ftp calls and all that junk is just terrible imo. the only time i would recomend someone do this little ftp "trick" is for an installer, which would only need to do this 1 time. but definately not for an operation repeated frequently while the website is in use.
safemode has limitations, and its not the ideal solution to shared hosting security issues. the php manual sais this itself. get it set up as cgi so you have controll over the php config, or dont create directories on the fly.
you could also use a database to store uploaded files. you wont have this problem then.