I had this same issue and it was driving me mad. I knew I had the proper permissions set up on the network's shared folder. I couldn't even install my application from my own machine via the network share. After searching long and hard for an answer I figured it out myself.
On the Publish tab of properties I only filled in the "Publishing Folder Location" with:
\servername\share\Application Folder
I left the "Installation Folder URL" section blank.
Somehow a field in the "Application Updates" section (via clicking "Updates" button on Publish tab) got filled in with a different value than what my network share was. Not sure if I did this myself or if it was set by default. I cleared out the "Update Location (if different than the publish location)" field and that fixed this issue for me. Here is a screen shot of where I changed the field:
I would post a screen shot of the form that was causing me trouble but for some reason I need 10 reputation points to post a picture.