Ha - I just went through the same kind of problem this morning. I reformatted my hard drive, and didn't realize (until I went to post) that I couldn't remember my WP admin password. My own stupid fault.
First I tried WP's "lost password" function, but it didn't work. I received an email saying that "user name [blank] 's password has been changed to [xyz]," where [blank] indicates a blank space, and [xyz] indicates the password. I tried this new password, but it didn't work. And checking the mysql database entry for admin in the wp_users table, I found that the "lost password" function was not, in fact, changing admin's password.
Next, I tried to change the password by manually updating the user entry, using mysql's built in "password" function. However, as you've already discovered, WP doesn't use the same password hash that mysql does, so this doesn't work.
After taking a break and wandering around my apartment in a frustrated daze, I had a tiny flash of brilliance. I crossed my fingers, and registered a new user "newuser" with password "newpass". I then logged into mysql, copied the password hash for "newuser", then manually updated the admin user's entry with newuser's password hash:
update wp_users set user_pass='newuserpasswordhash' where user_login='admin';
Worked like a charm.
- Erika