Showing "locating satellites" for hours while outside with clear view of the sky is really odd, and is more than just a caching issue. Unfortunately, this is something you'll need to contact Garmin support about again. Really odd that you had this problem before and are now having it with the new device. Hopefully they can figure out what's going on.
2 things you could try. If those don't work, you're only choice will be Garmin support.
1. Delete the CPE.BIN file and then leave it just sitting outside with clear view of the sky while trying to find satellites. It should find them within 5 minutes but I'd give up to 15. Not moving around should help it find satellites.
2. If that doesn't work, you can always try a full reset via the menu's settings\reset\reset default settings. This is a bit of a pain as you'll need to re-setup the device including pairing to your phone. Then try #1 again.
