Upload Woes

I just switched hosting accounts and I’m trying to get everything up and running again. My biggest hurdle (for right now) is that any time I uploading anything, I get the good old “Unable to create directory /wp-content/uploads. Is its parent directory writable by the server?”

I’ve been reading the forums and this is what I’ve got so far.

Changed the permissions to 777 recursively.

/wp-content/uploads shouldn’t have the leading slash.
I’ve tried changing this a dozen times, deleting cookies, restarting things. No dice. It seems like deleting that slash could be what I need to do, but I can’t do it. Any changes made to “Store uploads in this folder” don’t take.

I have php safe mode off.

Any help would be very, very, appreciated.

Thanks,
Martin