Have you tried reading the tip posted here:
http://www.n95users.com/forum/viewtopic.php?t=344
Go into Options -> View -> Satellite Info (in the nokia maps application)
and then see how many satellites come up. Also check what tracking methods you are using by going into the GPS Data application, and then choosing 'Options' then 'Positioning Methods'. Make sure you have a tick next to 'Internal GPS'