Uploading is not supported under SAFE MODE, because safe mode does not allow a script to write to any directories that it creates itself, which is quite stupid.
I would ask your host to disable safe mode, and if they don't, I'd personally consider them not worth paying for. It's a crippled PHP installation you've got there.
That said, you can still upload just fine using FTP, but I'm not sure about your clients...