Even without data / a-gps, any gps outdoors with not too obstructed view of the sky should get a fix in a few minutes - typically less than 5, theoretically, up to above 20 (fringe case, unlikely).

But if GPSMeeFo shows no sats, things are amiss for sure; well, at least if it's not an app bug. You could also try Track@Way free from the store, it also has some good GPS sat info screens.