Encontrei uma maneira de imprimir esses caracteres usando o código de idioma en_US:
Pressione Alt + F2 e execute env LANG=en_US gnome-terminal
. Então na janela do terminal:
$ printf '\xe5\xe4\xf6\n'
åäö
$
Isso indicaria que não há problema com a localidade, pelo menos, mas permite a codificação ISO-8859-1 conforme o esperado.
Editar:
A impressão usando o hexdump também funciona bem:
$ printf '\xe5\xe4\xf6' | hexdump -vC
00000000 e5 e4 f6 |åäö|
00000003
$