Grep может быть нестабильным с нечетными символами .. попробуйте:
grep --color='auto' -P -n "[\x80-\xFF]" record.txt | iconv -f utf-16 -t utf-16
Это может вернуть ваши буквы .. цвета будут потеряны. Возможно, стоит погадать с помощью utf-16 и utf-8.
И убедитесь, что ваша консоль поддерживает uft-8 и не назначена какой-либо настройке ansi.