Desde hace un tiempo Google ha pasado de regalar el acceso a los mapas a controlar el mismo, e incluso empezar a facturar a partir de un uso intensivo. Por eso ahora es necesario incluir en la petición una clave personal de acceso a los mapas. 
Para conseguir esta clave hay que acceder a la consola de desarrolladores de google y crear nueva credencial para google maps. 

Una vez hecho esto necesitamos editar un archivo en nuestro prestashop para hacer que los mapas funcionen.

El archivo en cuestión es controller > front > StoresController.php

Aquí modificamos la linea siguiente:

            $this->addJS('http'.((Configuration::get('PS_SSL_ENABLED') && Configuration::get('PS_SSL_ENABLED_EVERYWHERE')) ? 's' : '').'://maps.google.com/maps/api/js?sensor=true&region='.substr($default_country->iso_code, 0, 2));

añadiendo a la url tu Api key de la siguiente forma &key=APIKEYVAAQUIPARAQUEGOOGLELALEA

Quedando así:

            $this->addJS('http'.((Configuration::get('PS_SSL_ENABLED') && Configuration::get('PS_SSL_ENABLED_EVERYWHERE')) ? 's' : '').'://maps.google.com/maps/api/js?sensor=true&key=APIKEYAQUI&region='.substr($default_country->iso_code, 0, 2));

Es muy importante que cuando crees una nueva api key añadas a la misma restricciones para única y exclusivamente los dominios que la van a emplear. Si un usuario malintencionado emplea tu api key porque no está bloqueada te encontrarás, seguramente, con una factura inesperada. 

Manual de Google para obtener una api key