Why is Google MapView in my release signed android application works only on the emulator but not on my device

I've developed an android application which uses the Google MapView. during the development phase (with the debug key), the application worked fine both on the emulator and on my device.

Now, prior to releasing my application I've done the following steps:

1. Opened a new Google account (for the company)
2. Created a new key store using keytool for my release builds
3. Generated an MD5 for my 开发者_如何学Gorelease key (using keytool -list)
4. Registered the MD5 with the Google Maps API (http://code.google.com/android/maps-api-signup.html) while I was signed in using my new Google account.
5. Changed all the apikey elements of my MapViews to the newly generated one.
6. Exported my application from Eclipse using the ADT add-in (Project->Export->Export Android Application)
7. In the wizard, I signed my application using my release key.
8. Installed the application on my device using (adb install)

For some reason, the MapView is not loading any tiles, as if the key I entered is incorrect. I've repeated the above steps more then 3 times, for the same results.

Please Note,

1. My android manifest contains the INTERNET permissions
2. Nothing was changed other than signing the application.

Launching the application from Eclipse using the emulator, the MapView works great. even though the apikey element contains the key generated for my release keystore.

Any suggestions??