The very first fix is the slower one. It can be painfully slow (as long as 20mins!).
So just leave it on a table facing the sky alone and let it compute the fix.

This happens because it has NO cache about the satellites in view on your part of the world, so it has to look for them.
After the first fix has been done, the next one should be much faster (seconds or a bunch of minutes, depending of the quality of the signals).

It needs 3 satellites for a 2D fix and 4 satellites for a 3D fix.
I've heard that the GPS chip is a Sirf III, and that's a very good news as the fix time is greatly reduced with that chip (a part from the first one).

Let us know!