Mam dokładnie ten sam problem. Na Androidzie 4... GPS działał bez problemów. Po aktualizacji do 5.1 zaczęły się jaja.
U mnie wygląda to tak, że przez kilkadziesiąt minut (zwykle 20-40 FIX znika i się pojawia. Tu nie ma znaczenia jakich aplikacji się używa i w jakim trybie dokładności GPS się pracuje (ze wspomaganiem, czy nie). Po prostu znika i się pojawia. Nie da się przy tym użytkować nawigacji oczywiście, bo jak pozycja odświeża się co minutę, dwie - to jak niby w mieście nawigować?
Recepty póki co żadnej nie znalazłem.