Hi Mikal,
The most recent test had the GPS directly connected to the arduino and used USB power through ten feet of cable. No extra decoupling was used on GPS which was powered from the Arduino 5v line.
When connected to the Xbee shield, both the xbee shield and GPS were powered from a battery providing 5 volts.
My guess is that the problem is due to the GPS not getting full view of the sky. I will do some more tests later today. But I doubt it has anything to do with the library code.