Most hosts provide a site control panel or other means of offering a file
manager. I suggest using such a file manager or optionally any ftp or http
client to log into your domain and delete all the existing site files and
folders created by Publisher. Then attempt the upload. I would also suggest
asking your host to verify that the domain has permissions set appropriately
to allow Publisher to connect and write files/folders. You may think the
latter is not needed, thing is that it is not uncommon for a host to move an
account to another server or make other changes and to not implement the
same settings.
If you still have trouble after covering these suggestions then post back
the Pub version being used and whether you are publishing in ftp or http,
and the url of the site, and the host name.

I am having this EXACT issue with three different web sites on 2 servers.  
Did you ever get it straight?