Hi,
I also had an issue the first time i used Maps.
What Nokia doesnt tell you is that your phone doesnt actually come WITH Nokia maps.
You need to DOWNLOAD it from here first:
http://maps.nokia.com
Once you have downloaded the software onto your PC, you need to connect your phone to your pc in DATA TRANSFER mode.
Once connected, RUN the Nokia maps software on your PC and then follow the instructions to set it up, choose the maps you want and then choose the voice you want (will only work when you pay though).
It will then Download the maps and voice to your phone and when tell you when its done.
You can now disconnect your N95 from your PC and are now ready to try it out.
My N95 took a long time +- 10mins to connect to the satelites for the first time (i left it by a window and had a cup of coffee) but once it had locked on to the satelites for the first time, it now locks onto them quite quickly (1min - 3mins) depending on the weather. It even locked on during a very rainy day so it does work!
Nokia maps is quite good and i use it to show me maps while im traveling but if you want Voice, try
www.nav4all.com - i use it for navigation and it works like a dream and its FREE!!!
Hope this helps.