After I was fed up with using the administrative MySQL account on my local machine even though I had a personal account, I finally got to the bottom of why I was denied access to that user no matter how often I deleted, re-created the account and flushed privileges.

The problem occurs when you try to login and looks as if you entered the wrong password:

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

If you’re using phpMyAdmin, it looks like this:

#1045 Cannot log in to the MySQL server

However, I knew that I had granted privileges to that user with the wildcard host % so I could connect locally and also from anywhere else. Showing grants as root user:

mysql> show grants for 'username'@'%';
+---------------------------------------------+
| Grants for username@% |
+---------------------------------------------+
| GRANT ALL PRIVILEGES ON *.* TO 'username'@'%' IDENTIFIED BY PASSWORD '*2470C0C06DEE42FD1618BB99005ADCA2EC9D1E19' WITH GRANT OPTION |
+---------------------------------------------+
1 row in set (0.00 sec)

The root of this problem lies only in part with the custom user username. The actual problem is, that commonly upon setup of the MySQL server a few users are generated automatically, including the anonymous-user account (with privileges for wildcard host % as well as localhost). When you try to connect locally (which happens if you use command line or phpMyAdmin) with your custom user username, there are no privileges for such user connecting from localhost and therefore the connection is treated as an anonymous user (because such privileges do exist).
So in order to be able to use your custom user also when connecting from localhost, you need to create the same user (can be a different password, though) with the host localhost and grant the desired privileges:

CREATE USER 'username'@'localhost' IDENTIFIED BY 'your_password';
GRANT ALL PRIVILEGES ON *.* TO 'username'@'localhost' WITH GRANT OPTION;

Please see the MySQL Reference Manual section 5.5.2 Adding User Accounts about these reasons.
The issue was solved with the help of LinuxQuestions.org in this thread.