the only thing i can suggest is for you to look in the save function in changepasswd_sql.php and may be get it to dump out the SQL so you can try it manually and see where it is going wrong.
I have never tried the plugin with MD5 passwords so I dont know for sure how it will work but as I said all the "work" is done in the save function in changepasswd_sql.php - if you need to change any php, that is the place to do it.
Also you might want to look at the password plugin available in the trunk, as you might have seen on my webpage I am scrapping my plugin in favour of this one since it is much better.