Sometimes a "Cold Lock" can take a long time. Maybe upto 60sec. But subsequent locks should be timely.
Is the time on your phone correct? Do you have the proper Timezone selected?
Is the GPS enabled?
From the market, download GPS Test by Mike Lockwood.
Now Launch the program.
Press the Menu key.
Press Clear Aiding Data, then
Press Inject Time, then
Press Inject XTRA Data.
Go outside so you are under the unobstructed sky.
How long does it take to register a Lat/Long position?
SamanthaFarr, I can understand how troubling it can be not having your GPS working! Can you tell me what software version you are running? Have you ever been able to use any GPS services (i.e. Google Maps, Navigation)? Are you having any other issues with the device? Can you try run the phone in safe mode and retest the GPS http://bit.ly/Uq48Xi ^SP