I used to have the Garmin Forerunner 25 and the GPS took forever to acquire satellites. You might just be stuck with it.
Have you looked at this on the Garmin Support site?