GPS reboot

My Forerunner 45 (SOFTWARE VERSION 5.40) GPS does not work.  When I start a run, the Forerunner 45 says "A reboot is required to use GPS"  I reboot and the Forerunner says "Update failed.  Try Garmin Connect"  I have used the Garmin Connect app on a compute and it says the watch is up to date.