Arduino GPS shield giving incorrect altitude readings
I doubt that you somehow only damaged the logic that determines altitude in your GPS module.  

My best guess would be that your software is looking at the wrong part of the NMEA sentence the module is transmitting to your Arduino.  I'm not sure how the GPS shield is wired (there are seemingly a couple variants on SparkFun, but I'd attach a separate TTL converter (e.g. board with an FTDI chip) and look at what the GPS is actually sending.

You don't have to use the TTL converter, just get a glimpse somehow of the raw NMEA data.  The reason I suggest that is because I think the GPS uses the serial port that you'd normally use to talk with your PC.

The fact it worked before makes me think that either your software was modified initially then all the stock versions you've tried don't have that tweak in them, or you may have reconfigured the GPS module somehow to change the fields it transmits.