Трудно указать на ошибку, не зная, что вы уже сделали, но, по крайней мере, вы должны добавить библиотеку в свой манифест:
<uses-library android:name="com.google.android.maps" />
Вы также должны перейти в Window > Android SDK and AVD Manager
в Eclipse и убедиться, что устройство, на которое вы работаете, нацелено Google APIs (Google Inc.)
, а не Android x.x