I got this same error when installing to an actual device. More information and a solution to loading the missing libraries to the device can be found at the following site:
Fixing the INSTALL_FAILED_MISSING_SHARED_LIBRARY Error
To set this up correctly, there are 2 key files that need to be copied to the system:
com.google.android.maps.xml
com.google.android.maps.jar
These files are located in the any of these google app packs:
http://android.d3xt3...0120-signed.zip
http://goo-inside.me...0120-signed.zip
http://android.local...0120-signed.zip
These links no longer work, but you can find the files in the android
sdk if you have Google Maps API v1
After unzipping any of these files, you want to copy the files to your system, like-ah-so:
adb remount
adb push system/etc/permissions/com.google.android.maps.xml /system/etc/permissions
adb push system/framework/com.google.android.maps.jar /system/framework
adb reboot