Have you tried just leaving it on for a few hours? Sometimes, it needs to update the orbits of the satellites (for example, whenever USA goes to war, they adjust the orbits a bit to get better coverage over that area), especially a new device, and that may take some time. The satellites are on 90 minute orbits, so three hours should get most of them, and six will probably get them all. Once it gets current data, it will just keep itself updated on the go, if you don't shut off the GPS.