I've been doing some more testing:
After many reboot and test cycles the TTFF has been improving. Now it is more in the order of 5 to 10 mins.
Occasionally, after reboot it would not get a fix at all (waiting at least 30+ mins), with the only solution being a reboot. Maybe related to the bug mentioned by @rocket2nfinity ?
I also tested getting location this morning, having had a successful fix last night and no reboot in between. It only took 2 mins.
To give some more context: I haven't used the GPS much since my initial testing of this port in August (staying at home and all). At the time it worked well as @Flohack described. Recently I tried it again a few times and it was not working (hence my original post). Now I see that after many attempts it is sort of "warming up" and performing better. This is pure speculation from my part, but I suspect there is some kind of caching that helps the GPS get subsequent first fixes faster. Over time, if not used frequently, this information becomes outdated. Maybe this is why there is such thing as AGPS? (which, as far as I understand, is not available in UT).
Anyway, I don't think there is much more to do here. Maybe we should mark this as "solved". Thanks everyone!
I will keep doing some more tests. I'd be happy to help testing if there are any projects that aim to improve the overall performance of GPS on UT.