Just a couple of questions about this:
Is this your first time using the module? Or, have you used it before?
Did you test it outside with a clear access to an open sky?
Is the red light blinking or just steady on?
Have you tried performing the 'Cold Start' process?
Also, what is the firmware version of the board? To determine the version, please refer to this forum posting: http://www.usglobalsat.com/forum/index.php?topic=3514.msg8979#msg8979
The TTFF should take about less than a minute under optimal environment, which is outside with a clear view of the sky and no tall trees or buildings around.