MadMan, it definitely should work. I checked, the Desire has onboard GPS, and it should be as simple as opening Google Maps and your location will be displayed. Likewise, Google Navigator should work. It is an application that Google built that uses the Google Maps base, but implements it in a car-gps-navigator kind of way.
Google Latitude (what I think you're referring to by Locator) just sits on top of Google Maps, and permits your friends to see where you are and vice versa.
I have a HTC Desire Z running Android and use those apps, and they work without issue for me. So... on to trouble shooting.
Having maps isn't your problem; you're correct, Google Maps provides them for you. It will download the tiles you need when either using Google Maps or Google Navigator. Does Google Maps work at all? Like, can you open it and see a map?
Is the GPS turned on? Menu > Settings > Location > Use GPS Satellites tickbox.
Something to try is going to the Android Market and downloading Google Maps, in case yours isn't the up-to-date version. It will tell you if it is or not.
|