So, let's see the code.
+1
Many people have trouble modifying these libraries' example programs. They are a little "fragile", and frequently break when modified. I eventually wrote NeoGPS to be smaller, faster, configurable and more reliable, and the examples are correctly structured. Take a look at the NeoGPS Troubleshooting section for a description of the most common timing problems. A NeoGPS program is typically hundreds or thousands of bytes smaller, and uses hundreds of bytes less RAM. It can be almost twice as fast, but I don't think that's as important for your application (yet).
One problem is that other libraries deal with individual sentences, not the complete "fix" that is reported by the GPS device. Once per second, the GPS device will emit 5-10 sentences that contain various parts of a fix (see this table). After enough sentences have been received, the entire "assembly" of GPS information has been built. NeoGPS parses multiple sentences to fill out a single fix structure which contains all these pieces. NeoGPS returns one complete fix structure every second, not 5 or 10 separate sentences.
I mention this because the Arduino may have started up in the middle of an interval and received only the last few sentences. If those sentences didn't contain the speed field, your speed will be uninitialized, as PaulS suggested.
NeoGPS deals with this by having validity flags for each piece of information. If the GPS doesn't know the speed yet (or the sketch hasn't received it yet), the flag will be false. You can write code like this:
while (gps.available( gps_port )) {
gps_fix fix = gps.read();
if (fix.valid.speed) {
if (fix.speed_mph() > speed_limit ) {
// blinkies!
.
.
.
At startup, this flag will be false because the GPS device doesn't have a fix, or the Arduino hasn't received an RMC or VTG sentence (the only two with speed fields).
A secondary problem is that the NMEA checksum is not very good at detecting errors in the GPS data. For example, losing two of the same characters is not detected. Actually, flipping the same bit in any two characters will not be detected. So receiving "210" instead of "012" would not be rejected. -_- The Adafruit library doesn't even use the checksum.
The solution is to apply some common-sense rules like you suggested: startup time, satellite count, HDOP < 2, and filtering. Filtering takes advantage of the expected behavior of your platform, so you can reject changes in velocity that are too great (limited acceleration). Averaging can do some smoothing, at the cost of reaction time.
Another possibility is to use the binary protocol in the NEO-6M device. The checksum on those binary packets is very robust, and would almost certainly detect bad data caused by power issues or noise on the wires. NeoGPS supports the binary UBX protocol, which is definitely more complex than NMEA. The good news is that the packets are smaller, so there are fewer bytes to corrupt. UBX parsing is also faster than NMEA parsing.
BTW, you can send a UBX message to configure the NEO-6M to send GPS data up to 10 times per second. You don't need more than a few times per second, though. At higher update frequencies, the GPS library speed can make a difference.
To summarize: it could be uninitialized speed value, loop structure or data errors.
Cheers,
/dev