Problema instalando mysql en ubuntu

[wicd]

Hola, instale mysql-server en ubuntu, durante la instalacion en ningun momento me pidio que ingrese una contraseña para el usuario root, entonces lo que hago es :

$sudo /usr/bin/mysqladmin -u root password nueva_contraseña

Pero me deniega el acceso.

mysqladmin: connect to server at 'localhost' failed
error: 'Access denied for user 'root'@'localhost' (using password : NO)'