MySQL root password change

I have been trying to reset my MySQL root password. I have run `mysqld_safe --skip-grant-tables`, updated the root password, and checked the user table to make sure it is there. Once restarting the MySQL daemon I tried logging in with the new root password that I just set and still get *Access denied* for user 'root' errors. I have also tried completely removing and reinstalling MySQL (including removing the `my.cnf` file) and still no luck. What can I do next?