Try this:
The syntax clearly says that the password must
not be separated with a space from the '-p'. If you do, it takes our password as the database name. And of course, that won't exist.
Code:
mysql -u <username> -p<passwd> <database>
or
mysql -u <username> -p <database>
The second one will just prompt you for a password afterwards. Key it in, and voila![/code]