The GPS module never locks to the GPS satellite signal when connected to the Mega Board.
If the GPS module works ok if it is powered by an external source.
Main culprit could be power source noise from the RT7272 DC-DC switching modules. This modules oscillate at 500MHz that is nearly 1/3 of the GPS signal frequency. So signal jamming from the power source could be the problem in a mix of conducted or emited noise.
The GPS module has a ferrite ( PZ2012D800-3R0TF) in series for filtering.