Rehashed passwords after Drupal 6 upgrade fail

I had these 3rd party modules installed:
taxonomy_menu, adminblock, modr8, taxonomy_router, notifications, taxonomy_treemenu, blog_addons, openx, captcha, taxonomyblocks, token, pathauto, plus1, userpoints, google_analytics, invite, rules, views, ip_anon, jquerymenu, memcache, votingapi (1), messaging, tagadelic, workflow, xmlsitemap

All of them, except "votingapi", I've uninstalled before upgrade.

$drupal_hash_salt was added in d6->d7 upgrade process.

Update:
I've tested it three times on clean drupal 6.20 install (without content, third party modules, etc) on two linux hostings and I've got same results.

Steps to reproduce:
1. Install drupal 6.20
2. remove all files from www directory except sites folder
3. copy drupal 7-rc3 files to www directory (overwrite sites/README.txt and sites/default/default.settings.php)
4. Run update.php script
5. Go to front page
6. If you're logged in - logout
7. Login (success) - in this step password hash is changed in database
8. Logout
9. Login (fails)

Examples of hashes, etc:

drupal_hash_salt = XT9zxHAbF3leDXuG11tlRC_6nLoi-nTSH_jZxQNKqL0  (from settings.php; salt is created after access update.php)
password_hash_after_upgrade = U$S$9SNMppTgyxNnR3e2jdN2vfosDT/qDgLV7p5GNWRlO4yOfLmGl/yn
password_hash_after_first_login = $S$C8/FTF/6SFH63XaUOb.2NXx38Pbb2iAYhBI10A218WDQNnL0dQyf
password_hash_that_works = $S$C8/FTF/6SQaw4Bq4A8roVUSI0eFCQH1N/P9qUD1704KwS9c1x2zj (works after manually update in database: update users set pass = '...' where name='admin';

I've attached script that help me to find correct hash (used with drush scr).

I've checked how it works in API docs and find that user_authenticate() function use user_hash_password() function to get hash of plain-text password after upgrade on first login. user_hash_password() as $setting variable for _password_crypt() use random string generated by _password_generate_salt(). But user_check_password() as $setting use substr($account->pass, 1), and as $password - md5($password). But I'm not sure if this is the solution.

I've tested in on RC and -dev.

I temporarily made two changes in local copy of user.module (after upgrade) and it works. I'm almost sure that these changes will break something in a different place (registration?), so I don't attach a diff. But I think this may be helpful for module maintainer.

These changes are:
user.module#2186, function user_authenticate(), add line:

if ($new_hash) {
  $new_hash = _password_crypt('sha512', $password, $new_hash); /* change here */
  user_save($account, array('pass' => $new_hash));
}

user.module#412, function user_save(), comment line:

require_once DRUPAL_ROOT . '/' . variable_get('password_inc', 'includes/password.inc');
//$edit['pass'] = user_hash_password(trim($edit['pass'])); /* change here */
// Abort if the hashing failed and returned FALSE

#8: 1007504-upgrade-password-rehash.patch queued for re-testing.