Eu percebi uma maneira que funciona (não tenho certeza se é ideal). Correndo
ffmpeg -i broken.mp4 -pix_fmt yuv420p -crf 18 good.mp4
Cria um MP4 que é um pouco maior (provavelmente minimamente pior em termos de qualidade) ... e isso funciona no meu aparelho de TV.
(mas ainda estou procurando outras respostas, se houver alguma)