Hola
phyrian.
Puedes empezar por ver los permisos que tienen las carpetas donde instalas tu programa y los permisos sobre el registro de Windows. El problema está en ahí. Piensa que, si tu programa se ejecuta normalmente como usuario normal, éstos no deberían conocer las claves de administrador para ejecutar el update...
Una opción interesante puede ser dejar el Update como un servicio.
Si después sigues queriendo que se ejecute como administrador, puedes leer
este hilo donde se trató el tema.
Saludos.