Hey Lee! I think it may be folder based permissions... Here is how to fix it
You have open_basedir restrictions on your server. To get uploads to work you need to create a 'tmp' subdirectory under your main host directory and chmod it to 777. Then in the Admin CP set "Upload In Safe Mode?" to 'Yes' and point the "Safe Mode Temp Directory" to that directory. If you placed the tmp directory in the right place, the path to the Safe Mode Temp Directory will be:
Also the php.ini setting for 'upload_tmp_dir' is empty. It's possible you (as root) or your host will need to edit php.ini and set 'upload_tmp_dir' to point to the full path to a directory on the server that is chmod'd to 1777. You will also need to restart Apache after making this change.