To run the self signed map key, you need to have the app self signed as well. You also need to uninstall any previous debug version of the app before the self signed version will install.
If you're using eclipse, the apps run in the emulator are automatically debug signed.
To sign an app with your non-debug 'release' key, right click the project then select:
Android Tools->Export self signed application package, at the bottom of the menu.
This will walk you through producing a self signed .apk file in a directory. You then need to install the app. With the emulator running: adb install myapp.apk normally works well.