Looks like Google has launched a mobile version of Google Maps. Point your device to www.google.com/gmm to download the Java applet. They do note the following on the Support Devices page:

Maps does not currently work with Nextel, T-Mobile USA or BREW-enabled phones (e.g. Verizon, Alltel, U.S. Cellular), or Palm devices.

So make sure that you are not trying to use Google Maps on the above services and devices.  Too bad, I was kind of looking forward to this and from the list of “does not currently work” I take it that only devices on Cingular and Sprint can use the product.