A long delay in obtaining the very first fix is NORMAL. All GPS units need to have an up-to-date ephemeris table of each of the satellites it can see, in order to understand where the sats are. The ephemeris table contains the data about when and where the sat will be visible. Downloading that takes some time. Garmin says it can take up to 15 minutes, depending on how many sats your unit can 'see', when it first comes up. The table is good for some days and for a general location area, so if you leave the unit off for 2 weeks, or move it 500 klicks, it must re-fresh the tables. It must also do this the very first time it is turned on. That is why it is taking so long.

There are a variety of levels of start. A 'cold-start' is thought of as the first level, but in a cold start, the unit already has an ephemeris table. Think of 'first power-up' as more like a 'reset' start.
Analogizing to a browser, 'warm-start' is 're-load from Ram' (like 'Back'), 'cold-start' is 're-load from disk cache' and 'first-start' is 'load from the remote server'. It takes a while.