Mysql – How to disable anonymous login

According to the MySQL documentation, you can harden a MySQL server by adding passwords, or removing the anonymous accounts.

If you want to prevent clients from connecting as anonymous users
without a password, you should either assign a password to each
anonymous account or else remove the accounts.

Before hardening, my users table looked like this.

mysql> select user,host,password from mysql.user;
+------------------+-----------+-------------------------------------------+
| user             | host      | password                                  |
+------------------+-----------+-------------------------------------------+
| root             | localhost | *F3A2A51A9B0F2BE246XXXXXXXXXXXXXXXXXXXXXX |
| root             | gitlab    |                                           |
| root             | 127.0.0.1 |                                           |
| root             | ::1       |                                           |
|                  | localhost |                                           |
|                  | gitlab    |                                           |
| debian-sys-maint | localhost | *95C1BF709B26A5BAXXXXXXXXXXXXXXXXXXXXXXXX |
| myuser           | localhost | *6C8989366EAF75BB6XXXXXXXXXXXXXXXXXXXXXXX |
+------------------+-----------+-------------------------------------------+

I've remove all anonymous accounts, so that the user table now looks like this.
(I'm using puppet to manage the users, but puppet effectively performs a DROP USER command).

mysql> select user,host,password from mysql.user;
+------------------+-----------+-------------------------------------------+
| user             | host      | password                                  |
+------------------+-----------+-------------------------------------------+
| root             | localhost | *F3A2A51A9B0F2BE246XXXXXXXXXXXXXXXXXXXXXX |
| debian-sys-maint | localhost | *95C1BF709B26A5BAXXXXXXXXXXXXXXXXXXXXXXXX |
| myuser           | localhost | *6C8989366EAF75BB6XXXXXXXXXXXXXXXXXXXXXXX |
+------------------+-----------+-------------------------------------------+

Why is it that I am still able to login to my test system without a username or a password?
What do I need to do to prevent any unwanted users from logging in?

root@gitlab:~# mysql
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 98
Server version: 5.5.32-0ubuntu0.12.04.1 (Ubuntu)
....
mysql> 

Update:
I've also just discovered that I can login as root, without entering a password.

Update2:
I found this question which has some good information, but does not solve the issue.

There are no anonymous users.

mysql> select user,host,password from mysql.user where user='';
Empty set (0.00 sec)

I login as root@localhost.

mysql> select USER(),CURRENT_USER();
+----------------+----------------+
| USER()         | CURRENT_USER() |
+----------------+----------------+
| root@localhost | root@localhost |
+----------------+----------------+ 

I do not have a default password, or skip-grant-tables defined in my.cnf

root@gitlab:~# cat /etc/mysql/my.cnf |grep -i 'skip-grant-tables'|wc -l
0
root@gitlab:~# cat /etc/mysql/my.cnf |grep -i 'pass'|wc -l
0

Update3:

I have tried performing these steps with puppet, (which should perform a flush privileges automatically). I have also manually flushed privileges and also tried restarting mysql.

Update4:
I've also tried changing the mysql root password and flushed privileges. No luck, I can still log in as any user without a password.