Wouldn't all the old transactions then be compromised (because they could be trivially recomputed)?
After thinking about this some more, I've realized that breaking the hash function used in blocks would be more disastrous than I had originally thought. But it should still be possible to change the hash function "on-the-fly" by including secure hashes of each real block in the old chain with the new BitCoin release. Some mechanism of doing this (hopefully more elegant) would also have to be used for a gradual hash change.
Wouldn't the users lose their coins?
Everyone's balance is publicly available, so it should always be possible to preserve this data, no matter what changes are made to BitCoin.