The GPS reference frequency is accurate but has small variations (jitter) which are then averaged out by the following PLL synthesiser to give the final output frequencies. This works well when the jitter has a high enough frequency. I suspect what is happening is that some GPS reference frequencies have a very low jitter frequency which the PLL cannot average out. By changing the reference frequency slightly you are probably increasing the frequency of the jitter, thus allowing the PLL to work correctly.
The behaviour may well differ between individual units as the jitter will be dependent on the GPS receivers internal oscillator calibration.