Generally the NexStar, CGE, CGE Pro, CGEM and AS-GT with GPS module will successfully link with the GPS satellites in less than one minute. Occasionally the link may take a little longer, particularly if you have moved your telescope a great distance since the last use - hundreds of miles for example - or haven't used your scope in a long time. If it seems you have waited long enough and the scope still has not achieved a link, the most common problem is an obstruction between the telescope and the GPS satellites. For example, it is generally not possible to get a link inside a building. When outside, a building or a large tree can obstruct the signals from the satellites.
Also, be certain GPS is ON in the Utilities menu.
One other potential problem is a slight incompatibility between hand control version 2.2 and some of the earliest NexStar 8/11 GPS telescopes. HC 2.2 might query the GPS module before it is initialized. If this happens, you will not get a GPS link even if you wait for hours.
If have a NexStar 8/11 GPS and HC 2.2 and experience this problem, there is a workaround. After waiting a minute or two, if the scope doesn't link, press Undo until you are back at the initial startup prompt and start over again. If it doesn't link immediately, press Undo and restart the alignment again. Normally it will get the link the first time, unless you were just being impatient.
If none of this works, a cable needs reseated inside the scope (any cable or connector associated with the GPS board or GPS antenna). To locate the GPS board and antenna in the NexStar GPS, read this.