WHat do I do if it says 'could not create directory'?

Try changing the permissions on the wp-content directory to 766. If you still have problems, try 767, 775 or 777. Once your uploads are working, change the permissions on wp-content back to 755 again and check that everything still works OK.
http://codex.wordpress.org/Changing_File_Permissions

Try asking your hosts to check whether you have a folder ownership issue, Make sure that you include a copy of that error message when you contact to them.