Эта ошибка произошла со мной на реальном устройстве, а не на AVD, как в других ответах. В моем случае я работал на Nexus S с пользовательским ПЗУ, на котором не было установлено Google Maps.
Я прочитал в другом месте , что общая библиотека com.google.android.maps связана с самим ПЗУ и не является частью APK.
Поэтому решение для меня было вернуться к стоковому ПЗУ с установленными Google Maps.
Кстати, название этой темы относится к ошибке, обнаруженной в DDMS LogCat. Первая ошибка, которую увидит большинство пользователей (до проверки LogCat), будет в консоли Eclipse:
Installation error: INSTALL_FAILED_MISSING_SHARED_LIBRARY
Please check logcat output for more details.