Point of curiosity since there hasn't been a Garmin Firmware update for a couple of months and the connection problem started more recently, did your phone OS update around that time? If it did then then a phone OS change could be the issue. I can be a little hard on Garmin but it likewise would hard for Garmin to keep up with (or anticipate) every phone tweak that might come down the pike.
Either way, if you haven't done it, a simple power down restart is worth a try. Case in point, my 265 was getting about 90% of the way through finding satellites for GPS and never finishing, even setting stationary for 10 minutes. I restarted it, and the GPS connection was almost instant.
