Crie um atalho totalmente novo. Há uma dúzia de maneiras diferentes de fazer isso, mas uma forma explícita é clicar sobre ele no executável e escolher Criar atalho. Edite esse atalho para ser executado como administrador e arraste e solte ao lado do atalho não-administrador existente.
Eu tive esse problema eu mesmo; Eu precisava de um prompt de comando executado como administrador, mas não queria que todo prompt de comando fosse executado como administrador por razões óbvias de segurança ...
ATUALIZAÇÃO:
Acabei de ter razão para voltar a visitar este tipo de problema, por isso tive a oportunidade de testar várias combinações ...
Coloquei um atalho no menu Iniciar (no Windows 7) e o editei para ser executado como administrador - funciona. Eu também fixei-o na minha barra de tarefas (não como Admin) e também funciona como esperado, e quando eu uso o item de menu inicial original é executado como esperado (não como admin). Eu até criei uma cópia do atalho original, que executei como Admin, e novamente ... funcionou.
Eu acho que você precisa revisitar isso - minha solução funciona, e eu diria que faz mais sentido do que copiar executáveis.