head ou tail não corrigirá / alterará o caractere.
O que provavelmente acontece é que gedit tenta adivinhar a codificação do arquivo com base nos primeiros bytes. Quando esse 0xD4 está longe no arquivo, gedit supõe que o arquivo está em ASCII ou UTF-8 e queixa quando vê que o byte 0xD4 é inválido em ASCII ou UTF-8.
Enquanto para o segundo arquivo mais curto, já que 0xD4 está perto do começo do arquivo, gedit adivinha o conjunto de caracteres é algum conjunto de caracteres de 8 bits (provavelmente iso8859-1 onde 0xD4 é Ô).
Então, o seu:
head -n 449025 invalid.txt | tail > invalid_short.txt
O método está correto. Se você executar sed -n l em ambos os arquivos, verá nos dois casos algo como 0030020020024M . E com hd : 30 30 33 30 30 32 30 30 32 30 30 32 d4 4d |003002002002.M| .