Seems like it might be based on if you installed Froyo using CW or SP, but you can always try both fixes no matter how you installed.
See if this works and let us know.
Installed via CW:(credit-mrZoSo)
Using Root Explorer I did a search for maps
If you see it in /system/app/Maps.apk, move it out to your sdcard
Installed Maps using the apk just moved to sdcard
I ran maps and played in it for a minute, joined Latitude also from within Maps, just to make sure it worked and closed it.
Then went in to Settings>Applications>Manage applications>All, tap on Maps, tap Clear data, tap Uninstall
Went to Market and re-installed from there.
I did notice that after it installed through Market, Maps.apk does not show in /system/app or anywhere else, the only apk showing is /data/app/com.google.android.apps.maps-1.apk
Hope this helps, might have to do it a couple times, not sure. Seems to me the maps that is installed in the Froyo ROM is scrambled a little? for lack of better words, who knows,,,heh
Installed via SP:(credit-tanked)
Now after my install of Froyo: Maps wasn't accessible, I couldn't install it from the market, and wasn't in the Settings->Applications->Manage applications menu.
Once you mount your device with read-write access (with the adb) and give adb root privileges (once again, with the adb), you must edit the /data/system/packages.xml file. There is an entry that looks something like:
Remove this entry. Put the packages.xml file back on to your Droid and then restart. Then you should be able to install Maps from the market.
<shared-user name="com.google.android.apps.maps" userId="10028">
<cert index="13" />
<item name="com.android.launcher.permission.INSTALL_SHORTCUT" />
<item name="android.permission.USE_CREDENTIALS" />
<item name="android.permission.GET_TASKS" />
<item name="android.permission.WRITE_EXTERNAL_STORAGE" />
<item name="android.permission.ACCESS_WIFI_STATE" />
<item name="android.permission.ACCESS_COARSE_LOCATION" />
<item name="android.permission.GET_ACCOUNTS" />
<item name="android.permission.READ_CONTACTS" />
<item name="android.permission.CALL_PHONE" />
<item name="com.google.android.apps.maps.permission.PUSH_MESSAGE" />
<item name="android.permission.WRITE_CONTACTS" />
<item name="com.google.android.googleapps.permission.GOOGLE_AUTH" />
<item name="com.google.android.providers.gsf.permission.READ_GSERVICES" />
<item name="android.permission.DISABLE_KEYGUARD" />
<item name="android.permission.READ_PHONE_STATE" />
<item name="com.google.android.googleapps.permission.GOOGLE_AUTH.local" />
<item name="android.permission.INTERNET" />
<item name="android.permission.ACCESS_FINE_LOCATION" />
<item name="android.permission.MANAGE_ACCOUNTS" />
<item name="android.permission.VIBRATE" />
<item name="android.permission.RECORD_AUDIO" />
<item name="android.permission.ACCESS_NETWORK_STATE" />
<item name="android.permission.WAKE_LOCK" />
Here is rough step by step guide
Note: I am using a linux machine, hence no .exe after 'adb'. The commands should be very similar in Windows.
Just remember that the packages.xml file will end up in whatever folder you are executing the adb command from.
adb shell rm /data/app/Maps.apk
adb pull /data/system/packages.xml packages.xml
(now edit packages.xml with your favorite text editor and remove the maps entry)
adb push packages.xml /data/system/packages.xml