I had an identical problem with my old Sony Skymap GPS. It worked fine for about 1.5 years then would not get a lock to save its life. I dont think I was ever patient enough to wait more than 5 minutes before giving up. No problem, time to replace it as it did not output in NMEA.
I then got the Delorm Earthmate (USB). After a while this one exibited the same problems you described, it would take forever to get a fix but then it was ok (but not great), until I powered it off and back on. It would take anywhere from 5 minutes to 30 minutes to get a fix.
For my sony skymap GPS, some people said the internal battery could have gone dead. This battery maintained the last known location so that it did not have to do a cold start every time. I never bothered to look in the sony GPS. I did look for a battery in the Earthmate and did not see one. Even if it was the battery the cold start should be under a minute. Unfortunatly the car the Earthmate was in burned up so I no longer have that GPS to test.
It seems unlikely that the GPS location is the problem since it was working previously. Just to be sure, try hooking it up to your home PC such that the GPS has a view of the sky. If that works at least you can rule out the GPS hardware. If the GPS hardware looks good, check all your settings in your GPS software / port emulators if you use them. If they all look good then perhaps you installed something else in your car that is causing some serious interferance, perhaps new car stereo equipment? Maybe your carputer has a loose ground (I heard rumors this can cause interfance, who knows, double check it just in case).
If you hook the GPS up to your PC and it does not work even after you play with all your software settings, try different mounting positions. Try putting a large piece of metal under it and see if that helps. It may be a wive's tale that metal helps the signal but give it a shot. Did you splice into the wiring at all on the Holux to extend the cable or get power from another source? If so then maybe you need to replace your extended cable section with shielded wire. I once tried to extend some front panel audio cables with un-shielded wire and the results were disaterous. The shielded wire made all the difference.
Good luck and keep us up to date.