Sounds related. Do you have any multi-site modules like Domain or Domain Access?
I am wondering if either your site uses a different users table or if some other site is also accessing your users table.
But anyhow if users can't update passwords successfully, then it sounds like you have a basic Drupal problem, not necessarily related to CiviCRM. If you can fix that, then probably CiviCRM will work fine.