Si estás usando API V1 desde el día 3 de marzo Google no acepta Keys creadas con fecha posterior, así que por huevos vas a tener que usar API V2.
Lo cual además recomiendo bastante, es muchísimo más fácil de usar, más versátil, consume menos ancho de banda y el resultado final es 1000 veces más bonito.