Hola:
Las dos formas que conozco es mediante el efecto rollover, o con una imagen svg... lo del rollover necesita tantas imágenes como áreas uses. Aunque yo me decantaría con el formato svg. Puedes seguir usando la imagen png, y en vez de áreas se usan etiquetas polygon, envueltas en los clasicos enlaces, y con posibilidad de usar estilos del tipo :hover... el atributo a usar es fill.
Si buscas mapas de España (y svg), encontrarás algunas cosillas mías.
Saludos
