Wouldn't compromised crypto require entire block chain to be recomputed? If one of the cryptographic building blocks of Bitcoin were to be broken, couldn't that result in the entire block chain needing to be recomputed? And how would that work, given the computational expense involved?
If one of the cryptographic building blocks of Bitcoin were to be broken

This is a difficult question to answer because Bitcoin uses so many.
SHA256d
This is Bitcoin's main hashing algorithm. It uses it for proof-of-work, building merkle trees, and lots of other stuff.
Collision resistance
If broken, you could create two blocks that hashed to the same thing. This would be bad because you could give both out, and nodes would think that they agreed, but they were actually talking about different blocks.
Preimage resistance
If broken, you'd have essentially infinite hashpower, and you could do the previous attack on blocks that had already been mined.
Mining faster than brute force
Currently, the fastest known way to get a hash that starts with lots of zeros is to just run through that hash lots of times. However, if you could figure out at the start that certain ranges of nonces weren't going to result in a block, you'd have a significant advantage over ASIC miners, who wouldn't be able to change the way they mined.
HASH160
Collision resistance
Irrelevant.
Preimage resistance
If broken, you could steal bitcoins.
ECDSA
If broken, you could steal bitcoins.
Final remarks
It's unlikely that every crypto primitive that bitcoin relies on would be broken. If they were, there are usually better primitives that could replace them.