Can a cold storage bitcoin wallet become obsolete? Will a cold storage wallet always work?  What happens if the bitcoin protocol is updated? Is there a vulnerability in the protocol that could be changed to create this situation? Where is this formally documented?
There's a page in the wiki dedicated to Bitcoin's weaknesses. Specifically there's a section which describes what would happen if the cryptography would break. Linked is a forum post by Satoshi:


  If the hash breakdown came gradually, we could transition to a new
  hash in an orderly way.  The software would be programmed to start
  using a new hash after a certain block number.  Everyone would have to
  upgrade by that time.  The software could save the new hash of all the
  old blocks to make sure a different block with the same old hash can't
  be used.


In any case I do think that eventually it will become obsolete and you will have to transfer your funds to more secure public/private key pairs. Like Satoshi said, SHA-256 is very strong and could take several decades to break.  

On a positive note, the transition will be gradual and the community will have time to alert people about the change. This means that you'll have the time to eventually upgrade the keys in your cold storage.