I guess with whatever the SMPS IC you are using, the output capacitor should be able to help you to better extent on limiting the noise in supply. The reason for not tracking any satellite may not be directly related to the SMPS circuit I believe. It will be somewhere else.
Check if you have any metallic objects/ shields covering the GPS IC and the connecting antenna. If so, do away with these metallic objects and shields from the way of getting the signal from the satellites to the GPS IC, antenna.
Do the trial in an open area where you can see a better satellite signals on other reference GPS devices. Then try playing with the GPS antenna position to get some sort of satellite signalling in your proto.