When a ClickOnce application is set to "Full Trust", on install it will prompt the user to grant full trust. This means that the application will have all the same privileges on the computer as the user running the application (editing the regisitry, file io, etc). You mentioned in the comments that the app is set to full trust, so it would appear that it's not a security issue.
Are you certain all of the necessary files are getting deployed? I would just remove ClickOnce from the picture. Look at all the files in your deployment, create a folder and copy all those files into it, then try to run it. Does it work? My initial guess is that some needed file is not being included in the ClickOnce deployment.