Your users aren't using Kensington mice, are they? I know that sounds like a really odd thing to check, but we have been banging our heads against the wall for a week now onwhat looks like it might be the same issue. We deployed a couple ClickOnce apps to a group of beta testers and they work on all of their machines except one. On that one machine, clickOnce will download and install, but the app itself fails with no error message, event log entry, or anything to explain why. We finally stumbled on this post that gave us the unexpected reason for it.
http://blogs.msdn.com/winformsue/archive/2006/05/22/604103.aspx
so that gives you at least one thing to check