I was experiencing the same problem with Live Search. I am running the new Stock VZW MR1 updated ROM. It is entirely stock except for the boatload of apps which I have installed. GPS was working fine with Google Maps and TomTom 7.4, but not Live Search.
Anyway, I installed the PPST2.01.cab, ran it and then updated my PRL to 51143. Live Search is now finding sats in <10 seconds!
I did change GPS to com 4 in Live Search settings, but after switching it back to intermediate driver, it still works!
Hope this helps y'all out! After getting GPS to work on my first Titan, I just can't live without it.