Если кратко, то проверьте права пользователя на ветку реестра
\HKEY_CURRENT_USER\Software\Classes
(напомню, что ClickOnce при развертывании сохраняет информацию о приложении в ветке реестра HKEY_CURRENT_USER\Software\Classes\Software\Microsoft\Windows\CurrentVersion\Deployment)
И права на папку, в которой размещаются файлы приложения \Documents and Settings\USER_NAME\Local Settings\Apps\2.0
История появления и решения ошибки:
В результате шамански действий наших администраторов возникла такая ситуация:
Новый пользователь (I) имел свою учетную запись, но использовал профиль другого пользователя (II) (сделано было для экономии времени по переносу данных с одного профиля на другой и переустановки программ). В результате приложение ClickOnce работало, только если новый пользователь обладал правами администратора (что запрещено правилами конторы).
Проблема решилась в 2 этапа
Дайте права новому пользователю (I) , под которым развертывается приложение на ветку реестра HKEY_USERS\(Ищем ветку пользователя (II))\Software\Classes старого пользователя (II)!!!
Ну и конечно на папку c:\Documents and Settings\OldUSER(II)\Local Settings\Apps\ полный доступ (Для размещения ярлыка - то и на рабочий стол доступ дать тоже необходимо)
Удачи.
P.S. Еще была интересная проблема с развертыванием.
Сервер развертывания находился под управлением MS Windows Server 2008 R2 rus.
Клиент MS Window XP Enterprise SP3.
Проблема с развертыванием возникала в том случае, если в свойствах проекта на вкладке Application в поле Assembly Name внести название сборки на русском языке.
Номер ошибки я не могу вспомнить, но я нашел этот баг репорт на сайте MS, где была отписка - "Мы не смогли воспроизвести ошибку".
На Win7 приложение развертывалось нормально.