I would have thought an under voltage 7805 would be less stabilized.
Anyhow what sort of decoupling you got? if its a standard 7805 u would need a 100uF on input and a lower 10uF on output. Put a 100nF across the power supply to the GPS unit (as close as possible) and put a 100nF across the microcontrollers power too.
In my experience, there are much better things to use than a 7805. In your case, I’d try one of the simple switchmode boost supplies to bump your single LiPo cell to around 5.5V, and then use a good LDO 5V regulator (Micrel and Linear come to mind here) to take off the extra half a volt and smooth things out. Be careful to implement a low voltage shutdown, as Lithium cells HATE being deep discharged. Sprinkle capacitors everywhere, I like 0.1u ceramics for RF across all power leads, and 10u tantalum or electrolytic if the part sucks more than a few mA.The regulator and boost converter should be built with fat traces and a solid ground plane, and you should take care to read and follow the manf’s recommended layout and decoupling practices. A small ferrite bead inline with V+ can help sometimes too, or on both the input and output sides of the power supply.
That data dump looks to me like the rx lost a bit and was 1 bit off for the rest of the transmission. Make sure your serial cable is shielded and that the levels are 100% compatible, ie, don’t use a 3.3V CMOS serial output into a 12V bipolar RS232 input. Sometimes it will work, but reliability gets compromised 8)