JSON-то как раз точно не валидный, в валидном JSON кавычки должны быть, а не апострофы.

Вы покажите строку-то, которая присваивается из responseText.

содержимое php-скрипта, генерящего ответ от сервера:

<?header("Content-Type: application/json; charset=windows-1251");?>
[{"id": "501", "fio": "Агафонов Н.Г."}, {"id": "518", "fio": "Болобанова Т.В."}]

пробовал уже и с апострофами, и с кавычками... я же говорил, что содержимое php-ответа полностью совпадает с содержимым строки data в первом примере, который работает БЕЗ ошибок, т.е. валидность JSON вроде бы ни при чем.

У вас перенос строки здесь.

не понял где перенос строки?
кстати, попробовал сделать так:
Закинул в php строку вида "100:name1,200:name2", разобрал с помощью split, все работает без ошибок (идея с http://www.internet-technologies.ru/...ticle_526.html). Смущает только то, что, во-первых, это как то нестандартно, а во вторых, я еще хочу атрибуты к <options> прикрутить (доп. данные кроме атрибута value).

После отправки заголовка у вас идёт перенос строки. А в JSON не может быть переносов строк.

Хотя он тут не причём. Но убрать надо.

а если просто скачать содержимое, то что там?

Вобщем покажите, что в Firefox-е покажет

alert(JSON.stringify(xmlHttp.responseText));

Выглядит вроде как валидно, может попробовать кодировку на utf-8 поменять?

менял, получаем все то же самое, только кракозябрами