I am not sure how you are setting the password but I think the problem is that you are not encrypting it when you do. When I select user, host, password from mysql it shows like this:
mysql> select user, host, password from user;
+----------+-------------------+-------------------------------------------+
| user | host | password |
+----------+-------------------+-------------------------------------------+
| root | localhost | *C76723A25A4C3CBCB1ABE27DF249CB2FE5D93C6D |
| root | lptp1.txlinux.com | *C76723A25A4C3CBCB1ABE27DF249CB2FE5D93C6D |
| root | 127.0.0.1 | *C76723A25A4C3CBCB1ABE27DF249CB2FE5D93C6D |
| | localhost | |
| | lptp1.txlinux.com | |
| vpopmail | localhost | *A455CE2217E33E0F6BBFF1CC93FEEADD81E612D4 |
| walkindb | localhost | *2717916A73F7E5F932F40E12B46963B6F60BB3D3 |
| sitdb | localhost | *CFA0B33EE5F4E9CC9B19807BE646CADA177B04FD |
+----------+-------------------+-------------------------------------------+
8 rows in set (0.01 sec)
Try using the following to reset the root password when in safe mode:
UPDATE mysql.user SET Password=PASSWORD('root123') WHERE User='root';
FLUSH PRIVILEGES;