Cuando mi aplicación intenta usar la API de Google Maps, aparece el siguiente error de logcat tan pronto como intento acceder a los datos de la API de Google Map (¡desplácese hacia la derecha para ver las cosas buenas!):

02-02 15:39:35.329 23868-24511/com.somepackage.name E/Google Maps Android API: Authorization failure.  Please see https://developers.google.com/maps/documentation/android/start for how to correctly set up the map.
02-02 15:39:35.339 23868-24511/com.somepackage.name E/Google Maps Android API: Ensure that the following correspond to what is in the API Console:
                                                                                            API Key: AI~~~~~~~~~~~~~~~~~~~~~~~~~~ZwmI​
                                                                                            Package Name: com.somepackage.name
                                                                                            Certificate Fingerprint: 50:~~~~~~~~~~~~~~~~~~~~:D5

Aquí hay una imagen de la Consola de soporte para desarrolladores de Google con la huella digital y la clave API (¡y sí, coinciden!). También he esperado que los servidores de Google se actualicen (5 minutos según el dox; he esperado horas).

Y aquí está el AndroidManifest.xml principal de mi proyecto (editado por brevedad):

<?xml version="1.0" encoding="utf-8"?>
...
<!--
 The following two permissions are not required to use
 Google Maps Android API v2, but are recommended.
-->
<uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />

<application
    ...
    <!--The key to use Google's map API -->
    <meta-data
        android:name="com.google.android.geo.API_KEY"
        android:value="AIz~~~~~~~~~~~~~~~~~~~~~~~~~~~~wmI​"/>

    <activity
    ...
    </activity>
    ...
</application>

Tengo una cuenta de Soporte Premium con Google, pero hasta ahora no he podido contactarlos. ¿Alguien tiene alguna idea de por qué recibo este error de autorización?