Isso parece que suas regras de agrupamento de localidade são muito ... úteis.
Experimente com
LC_ALL=C grep [A-Z] input.txt
para testar essa ideia.
Eu tenho
export LANG=en_US.UTF-8
export LC_COLLATE=C
export LC_NUMERIC=C
na minha inicialização do shell para evitar esse tipo de problema enquanto ainda obtém minha bondade unicode.