From the home screen, hit menu, settings, applications, manage applications, tap maps, and try to uninstall that way. Then you can update through the market.
If that doesn't work, use a 3rd party app to remove the maps apk. Root explorer is what I use, just find the file, and rename it first (maps.apk.old), then download the new apk from the market, then you can remove the old file from your phone.
what Rom are you running? have you tried flashing a gapps package? or rename the file ext. to .bak on the original in the system/app folder? I believe gapps like maps must have an original copy in the system/app folder, then any updates in the market will install to the data/app folder. not sure if it will work but if you can find the apk push it to /system/app then try updating and see how it works