Android Maps: Installation error: INSTALL_FAILED_MISSING_SHARED_LIBRARY

I'm trying to use Android Maps, following the instructions in Hello MapView.

I've added in the Manifest, and I'm building against the 'Google APIs' target, which claims to be API version 7.

So I don't think I'm doing anything obviously wrong, but the project refuses to build with this error:

[2010-12-22 13:34:32 - FMS]Installing FMS.apk...
[2010-12-22 13:35:01 - FMS]Installation error: INSTALL_FAILED_MISSING_SHARED_LIBRARY
[2010-12-22 13:35:01 - FMS]Please check logcat output for more details.
[2010-12-22 13:35:01 - FMS]Launch canceled!

logcat is telling me the following (not very enlightening):

D/PackageParser(   55): Scanning package: /data/app/vmdl67147.tmp
I/PackageParser(   55): com.android.fms: compat added android.permission.WRITE_EXTERNAL_STORAGE android.permission.READ_PHONE_STATE
E/PackageManager(   55): Package com.android.fms requires unavailable shared library com.google.android.maps; failing!
W/PackageManager(   55): Package couldn't be installed in /data/app/com.android.fms.apk
D/AndroidRuntime(  206): Shutting down VM

It is possible I haven't set up the Maps API key correctly - when I got it using keytools, I didn't specify an alias_name, though this didn't seem to cause an error.

Can anyone help?