The problem _is_ in the hardware. As far as I can tell, the TI 5300 chip does not bother to store almanac data. The chip also requires at least 4 satellites to obtain a fix, when most (all?) other chips only need 3.
Hey there . Give me some credit too. I was the one to discover the problem. Jussi found a fix for it.