What are some good examples of modifying crypto where flaws are not really obvious?
One of the best examples that I know of is "chained CBC" as used in SSL. This looks exactly like regular CBC. The only difference is that instead of sending a new IV with every message, the IV is taken to be the last ciphertext block of the previous message. This is much more efficient since for small packets you don't need to send a large IV each time. In addition, you don't need to generate new randomness for every message (and rely on the randomness on the machine). This looks just like CBC since a single long message exactly has the "chain" effect.

However, this minor modification (and major optimization) is not secure, and resulted finally in the BEAST attack on SSL.