Android Geocoder.getLocationFromName () throws IOException: Servicio no disponible en Device

Estoy utilizando el método Geocoder.getLocationFromName () en el emulador y mi teléfono (Nexus S con Android 4.1) y obtengo la siguiente excepción:

java.io.IOException: Service not Available 

Hay una serie de preguntas acerca de esta aparición en el emulador ( ejemplo ), y la mayoría de ellos dicen que es una versión específica del emulador que tiene el problema. Sin embargo, la excepción aparece en mis AVD (2.3 y 4.1) y en mi teléfono.

• ¿Cómo notificar al usuario cuando entra en alguna región usando Geoloqi API?
• Android - Geocoder.getFromLocationName () no funciona en el dispositivo ICS
• Android - ¿Cómo obtener la ubicación actual (latitud y longitud)?
• Cómo obtener latitud y longitud de la dirección en android
• Geocodificación inversa - Servicio No disponible - Reiniciar el dispositivo que no resuelve definitivamente - criticar mi geocodificación inversa manual

Tanto mi teléfono como los AVD tienen conexión a Internet. Mi versión de la API es 16 (android 4.1), pero también intenté con los más viejos. Ambos AVD incluyen API de Google.

¿Alguna idea de lo que está pasando aquí?

Este es el fragmento de código relevante:

 Geocoder myGeocoder = new Geocoder(getApplicationContext(), Locale.getDefault()); List<Address> newAddresses = myGeocoder.getFromLocationName(arg0.toString(), 10); 

Y este es mi manifiesto:

 <?xml version="1.0" encoding="utf-8"?> <manifest xmlns:android="http://schemas.android.com/apk/res/android" package="com.asdasd" android:versionCode="6" android:versionName="1.3.1"> <uses-sdk android:minSdkVersion="16" /> <uses-permission android:name="android.permission.INTERNET" /> <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" /> <uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" /> <application android:icon="@drawable/ic_launcher_asdasd" android:label="@string/app_name"> <activity android:name=".AsdasdActivity" android:label="@string/app_name" android:screenOrientation="portrait" android:windowSoftInputMode="stateHidden"> <intent-filter> <action android:name="android.intent.action.MAIN" /> <category android:name="android.intent.category.LAUNCHER" /> </intent-filter> </activity> <activity android:name="com.google.ads.AdActivity" android:configChanges="keyboard|keyboardHidden|orientation" /> </application> </manifest> 

 # Project target target=Google Inc.:Google APIs:16