Olá Patrício
Para resolver seu problema, você pode utilizar uma outra versão do AddOrUpdate que recebe um lambda que devolve qual é a chave que o EntityFramework deve considerar para fazer o Update http://msdn.microsoft.com/en-us/library/hh846514(v=vs.103).aspx. Supondo que o seu utilizador tenha um nome único, podemos utilizar a seguinte chamada:
context.Utilizadores.AddOrUpdate(utilizador => utilizador.NomeUtilizador, new Utilizador 
{
   NomeCompleto = "Administrador do Sistema", 
   NomeUtilizador = "admin", 
   PalavraPasse = new_password 
});
A versão que você utilizou no código tenta procurar a chave primária do objeto que foi passado dentro do banco de dados, mas como a entidade passada não possui o campo de chave preenchido, o EntityFramework assume que o objeto é novo e por isso faz um insert.