Kan ikke logge på som root (MySQL)

Jeg er ved at installere MySQL, jeg kører "apt-get install mysql-server mysql-client" og trykker Y.
Imens den installerer spørger den efter et root password, jeg giver den et, og bekræfter det bagefter.
Når installationen er færdig kan jeg så ikke logge på med den adgangskode jeg har valgt. Jeg søgte på "Forgot mysql password" på Google.
Jeg prøvede at stoppe mysql daemon og starte den sådan: "mysqld_safe --skip-grant-tables" som gør at man kan logge på som root uden brugernavn og adgangskode.
Derefter går jeg ind og skriver:

zeroyear2:~# mysql
>UPDATE user SET Password=PASSWORD("NEWPASSWORD") WHERE User='root';
>FLUSH PRIVILEGES;[/quote]

Terminalen svarer at ændringen har taget effekt 0 steder.
Jeg prøver at logge ind alligevel (Efter at have genstartet mysqld normalt) men uden held.
Jeg har googlet og googlet, men jeg kan ikke finde nogen med det samme problem, da det er svært at finde nøgleord til 3 linier tekst, som sagtens kunne passe til en masse andre fejl.