I finally did get it to install through the Market.
Using Root Explorer (its only a couple of bucks in the market) I did a search for maps
/data/app/com.google.android.apps.maps-1.apk -you might not have this entry, it's OK
If you see /system/app/Maps.apk, move it out to your sdcard [If you dont have it you would use the maps in the link at the beginning of the post]
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.
Went in to Maps, got Login failed- that's OK, clicked on join Latitude now you should see a Notification(in Notification bar up top) asking for permission, accept it and your good to go now.
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
EDIT: Verified this method worked on the second release of Froyo as well.