Without seeing a datasheet on the device you are using, I would question this:
// WIRING:
// 1. GPS is powered and Grounded. After about 20 seconds the GPS achieves lock.
// GPS lock is indicted by a solid red light.
// 2. GPS TX (blue wire) is connected to Mega 14 (Tx3)
// GPS RX (yellow wire) is connected to Mega 15 (Rx3)
Normally the Tx on one device is connected to the Rx on the other device.