Essentially, the entire transaction history of the current blockchain would become the "genesis block" of the new system.
Thus, transaction records up to that point would be lost? That would technically relatively simple, and probably the task of migrating the whole blockchain is not feasible.
I was looking for a scenario where for example Bitcoin would need to start using Scrypt or Cunningham chains PoW technology. Just how big a mess would that be, if transactions are pruned would the genesis block retain address balances?
Lets try this again...
What would be done with the transaction history would depend on the developers of the new protocol.
The simplest thing to do would be to leave it exactly as it is, with nodes recognizing a particular block height as the point to begin using the new proof-of-work.
It would also be possible to strip all the unnecessary data (blockhash, nonce, etc) out of the blockchain, and accept the new trimmed down blockchain as a transaction history.
If the change is big enough and significant enough, its quite possible that it will just be implemented in a competing crypto currency and people will just transition from one currency to the other over time rather than modifying bitcoin. It is far too difficult to get a consensus on such a significant change.