HOWEVER, in your situation it appears you have manually deleted one of the apps. Depending on if you did this in system/app...not good and a waste of time, because my Zip or Patch will overwrite that one anyway.... or in data/app (where normal Market apps are installed).
Either way, there is now only one way to really be sure both versions are deleted and clearded from the phone to elimiate conflicts. Follow these steps to get back on track.
You will need Root Explorer to do this easiest (all Rooters should have this app, if not GET IT).
#1- Go to system/app and look for Maps.apk. If it is still there, leave it. If it is not there, well it doesn't matter now, it just means you will lose any user data..not a big deal, if you have backed up Maps data via Titanium Backup (another Rooter must have).you can restore it AFTER installing the Patch/update
#2- Go to data/app and look for com.google.androidapps.maps.apk (or similar, just makes sure the last part of the file name is "maps") ...DELETE this file.
#3- Follow the original steps of going to Menu>Setings>Applications> Manage Applications and again look under downloaded for Maps...OR the file name you deleted ie. com.google.blahblah.maps.apk ... if you find either of those, open it and select "Uninstall" or "Uninstall Updates", which ever option you have.
After you have verified all of this then install the Patch/Update zip and you should be all good to go.