Ok, so this is why it does not work. It need the MapView API.

http://code.google.com/android/toolbox/apis/mapkey.html

Solca, it looks like you have to register with them so you can distribute it. I will see if I can rip it from the emulator though, for a temporary workaround.

Also, it looks like some guys are trying to make as OpenStreet version of MapView API, so we can overcome this obstacle.

Edit: Never mind, it won't be that easy. The OpenStreet program I linked to later does work though...