The first time I ran blackberry maps..it took a minute or two to lock in on a satellite. You just have to be patient...
As for google maps...that took even longer the first time I installed and ran the application. Ever since, its been locking on a satellite within ten or fifteen seconds.
Try letting it load for a while the first time...it should be ok after that.
If you continue to have problems...it could just be a hardware defect.