Как получить имя-фамилию юзера кириллицей?
Разобрался. 
Мой сервер «звонит» на api.vk.com с помощью curl. Нужно явно указывать принимаемые языки в HTTP заголовке Accept-Language.
Может, влияет географическое расположение сервера: гоняю с амазоновского EC2 где-то в Вирджинии. И VK решил, что раз так, то отвечать лучше «хэллоу!».

Строка, вернувшая кириллицу в ответы VK api:
curl_setopt_array( $ch, array(
    CURLOPT_HTTPHEADER => array('Accept-Language: ru,en-us'),
    ...
));

Документация по опциям curl.
Транслит на google code