Mysql – Root is not allowed to grant privileges on a MySQL database

I have a MySQL database and I am not able to grant permissions to users on newly created databases when logging in as root.

mysql> create database test1;
Query OK, 1 row affected (0.00 sec)

mysql> grant usage on *.* to 'test'@'%' identified by 'test';
ERROR 1045 (28000): Access denied for user 'root'@'%' (using password: YES)
mysql> show grants for root;
+--------------------------------------------------------------------------------------------------------------+
| Grants for root@%                                                                                            |
+--------------------------------------------------------------------------------------------------------------+
| GRANT ALL PRIVILEGES ON *.* TO 'root'@'%' IDENTIFIED BY PASSWORD '*hash_is_here' |
+--------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
mysql> select user();
+-----------------+
| user()          |
+-----------------+
| root@172.17.0.4 |
+-----------------+
1 row in set (0.01 sec)

So as you can see, I can log in as root, root has all privileges on .. Any ideas how could this happen? I haven't upgraded MySQL while keeping the data (I know that this could be caused by upgrading from 5 to 5.5). Thanks.