Voltage decreases on higher current
Have you considered the peak current taken by the GPS module - it will take short pulses of current in the order of a couple of amps. Average is one thing but peak requirements (even though very short in duration) can cause your regulator circuit to get out of shape. Try putting a big decoupling capacitor (maybe 1000uF) on the power terminals to the GPS.