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.