Добавьте в ваш скрипт:
req.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded*!*; charset=utf-8*/!*')
а на вашу страницу:
<meta http-equiv="Content-Type" content="text/html; charset=*!*utf-8*/!*">
Ну, и заодно, сам index.php конвертнуть в utf-8. Только без BOM
Можно и windows-1251 использовать, но чтобы везде было одинаково.