If the password you provided was wrong, you'd see something along the lines of
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)
The error you're seeing suggests the MySQL server isn't actually running. If you're on OSX, and you've got the PrefPane installed, check in System Preferences that MySQL is started. If you're on some Unix flavour, as tsabz suggested, check that the mysql daemon is running. If not, something like sudo /etc/init.d/mysql start
should sort you out.
EDIT: Your edit suggests you are definitely using the wrong password. If you've not set a root password, just use mysql -u root
which means you're not providing a password. If you can't remember your root password and need to reset it, check out this link, section C.5.4.1.1. http://dev.mysql.com/doc/refman/5.0/en/resetting-permissions.html