Make sure you're using the correct password. It shouldn't be a permissions issue if it is a clean install and you are connecting as root. Also, you don't need to specify a database to connect to. (And using the `mysql` database directly is generally a very bad idea...)
shell> mysql --user=user_name --password=your_password db_name
The (using password: NO) part of your error is telling you that either 1.) you are not entering a password, or 2.) you are trying to enter the password incorrectly. Just for kicks, try using the --user=user_name --password=your_password syntax.