Suppongo google si aspetti dati in utf8, mentre tu glieli passi in euc-jp.

prova a fare un $query = mb_convert_encoding($query, "EUC-JP", "UTF-8"); prima di passare la $query a google..
Se non hai l'estensione mbstring, fai la conversione con iconv.
Naturalmente anche la tua pagina dove vengono visualizzati i dati deve essere in utf-8.