I needed to change magento admin password so I went through following steps:
1)I exported the admin_user table into mydocumnets.
2)I run this Query:
UPDATE admin_user SET password=CONCAT(MD5('qXpassword'), ':qX') WHERE username='admin';
Can you show your admin_user table before adn after updating? Not all, just row with user, that you try to modify.
Also, try to use SHA2() instead MD5() in your SQL query. Tell please, if it works for you.