I’m running the MarsDroid ROM on an HTC Magic from Three in Australia.
I saw that a new version of Google Maps came out (4.1.0) that I wanted to try, but I couldn’t update via the market.
This is what I did to get it running:

geoff@desktop:~/android-sdk/tools$ ./adb root
geoff@desktop:~/android-sdk/tools$ ./adb remount
geoff@desktop:~/android-sdk/tools$ ./adb shell ls /system/app/ | grep map
maps3.4.0-brut3-MT.apk
geoff@desktop:~/android-sdk/tools$ ./adb shell rm /system/app/maps3.4.0-brut3-MT.apk
geoff@desktop:~/android-sdk/tools$ ./adb uninstall com.google.android.apps.maps

From there I was able to install successfully from the Market.
The version that shipped with MarsDroid has navigation outside the US, but since I don’t really use it, I wasn’t too fussed.