The reasoning is fairly obvious - they dont want to see dumb missiles getting upgraded to a DIY guided ballistic missile thanks to a $100 Garmin gaffa taped to the side and a cheap flight control computer.
The intention was for a GPS device to disable itself if it was traveling faster than 1k knots AND above 60k feet, not traveling faster than 1k knots OR above 60k feet. Unfortunately, many GPS devices improperly implement this as an OR condition, rather than an AND condition. This becomes problematic when using a GPS in a high-altitude weather balloon to determine altitude and location, which a few friends and I did a couple years ago. We had to be very careful when selecting the GPS we used to avoid this pitfall.
We used a UBlox5, which we purchased from diydrones.com. This was in 2009, so that particular model is now outdated. Both Adafruit and SparkFun now sell devices which are explicitly listed as being HAB-friendly. There's also good guide at http://showcase.netins.net/web/wallio/GPSrcvrsvs60kft.htm. That page states that SiRF-I and II are known to fail above 60k feet, and that some SiRF-III-based receives fail, while others don't.
(If you happen to be in the Bay Area, I'd be happy to meet up and give you guys some pointers sometime; drop me a private email.)