Jag fick samma fel när jag lät en widget kommunicera med phpscript på datorn. Jag kom fram till följande två sätt att lösa problemet. Båda två funkar var för sig för mig men gissningsvis är kanske ettan att föredra för dig eftersom tvåan förstör responseXML.
1 kör utf8_encode() på allt du skriver ut med print och/eller echo samt utf8_decode() på alla variabler du skickar till scriptet. Min teori är att php arbetar med Latin1-kodning internt, åtminstone verkar php göra det på min dator.
2 kör urlencode() på allt du skriver ut med print och/eller echo. Kör sedan unescape() på responseText i javascript (se bara till att själv ersätta de tecknen som javascripts unescape hoppar över, såsom +). Samma sak åt andra hållet, kör escape() i javascripten först och urldecode() i php när du tagit emot något från javascriptet.