OK I think I've cracked it!
I've done a successfull test on my local dev environment under 5.0.1 and the immediate problem of not being able to add markers does not happen with the new DotNetNuke.Modules.Map.dll i have built.
However, now comes the tricky part. I don't have a production environment running 5.0.1 that I can test this on so I'm afraid it'll be down to you folks to test if it works on your installation. I have built a release version of the DLL and uploaded it in a zip file on my FTP server here. The username and password are the same - dnnMap (note the capital M!).
First, and most important, please back up your site. Obviously, you're agreeing to test this at your own risk and I accept no liability whatsoever for any problems with it so please don't skip the backup step!!
Next, replace the existing DotNetNuke.Modules.Map.dll in the bin folder of your website with the version in the Zip file.
You may need to restart your application using the HOST Settings screen before the new DLL is picked up but I'm hoping that once you recycle the site, you should be able to go in and add a marker on the Interface panel. Please can you check this, and also check that you can edit the marker after. Obviously, you should test as comprehensively as possible here as I have been focussed on this particular scenario and haven't been checking to see if anything else breaks. As I said before, I'm not part of the project team and don't have access to test scripts etc!
Anyway, please let me know if this works for you. There's a possibility I may need to rebuild a couple of other DLLs that depend on this but I'm not sure on this so I'll need your feedback!
Fingers crossed it works for you...