the 35 seconds figure quoted is only valid if it can actually see signals from a suitable number of satellites. usually when it first sees a satalite it receives what's called an almanac which tells it where to find other satelites at any given time of day.
You need signals from three satelites to get a position fix in 2 dimensions and 4 to get a 3 dimensional fix, most GPS receivers will start to generate the PPS signal one they have a 3 d fix and that will continue until it looses all signals.
if your receiver is not in a good position to get a signal from 3 or 4 satelites then that's what's causing the delay.
Older garmin modules are particularly bad at getting a quick fix in anything but perfect conditions, newer modules use the much more sensitive SirFStar chip set which is much better in weak signal conditions.