pek

Yeah, it would be weaker against a collision attack. But that shouldn't be a concern as the purpose of the password hashing function is to protect against a preimage attack: finding the password given its hash. I can't see how the composition could be more vulnerable to a preimage attack than its parts. (Provided that the inner function's output is evenly distributed.)

Couldn't you just move from, say, using MD5(password) to bcrypt(MD5(password))? So when it becomes apparent that the old hash is no more secure, start using the combination of the old bad hash (MD5) and the new good hash (bcrypt). This way you can simply run once through the password database, hash each password hash there with the new better hash, and throw away the old hashes. No need to prolong the process until the users log in.