MattS You should always have a test site as a working model just in case you need to alter anything or have it as a back up.
Test Site on your Localhost :
Bascially you set up your PC as a host/web server, very simple to do using apache and php, if you do not understand that use an old version of XAMPP version 1.4.16 which installs what you need. Then you can setup a ZC store on your PC and access it via your browser using an address like http://localhost.
Then you can see if you can upload the data using EP. From this if this works it would be a hosting issue.
I am not an expert in hosting but it seems to look as if it is a hosting issue if it works for the host but not for you,as it should either work or not whether a remote user or a server side user. Possible look at another hosting company, Look at the certified hosts on this site I use one and they are excellent without any issues. Ask them if they have any issues with large stores like yourself before you commit, if they specialize in ZC they should beable to answer your question.