Stuck at middle of Install

[Largo]

Ok i've followed the install instructions and i'm stuck at the middle where you need to enter a password in after mysql_secure_installation

I'm running a Debian 5 Lenny 64-bit OS on a Xen VPS.

That being said i remembered the password, but every time I enter the damn thing i get this.

Code:

ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)

If i don't enter a password and just hit enter, I get this.

Code:

ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: NO)

I've done a couple searches in the forums, but they only go far as to say this is a problem while updating, I am not trying to update, I am trying to install the software. Any help would be appreciated!