Hi,
Which iPad hardware version ? (3, 3GS, 4 etc.)
Is its software up to date ?
Is it jailbroken or clean ?
My guess would be out of date software and you're missing a bug fix, if not, might be worth trying a full reboot (turn off/on) just incase it's a little confused.
Otherwise, perhaps cycle location and GPS related settings in the preferences screens.
Are you trying these tests indoors our outside with a full 360 degree low view of the sky ?
If none of that works, then it might possibly be a hardware fault....