Upload Folder

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. Similarly, I can’t change the “Store uploads in this folder” to anything but /wp-content/uploads.

Any help would be very, very, appreciated.

Thanks,
Martin