Is your TV a Samsung ? Samsung and a couple of other brands had problems with header stripping.
EDIT: I'm reading it again and indeed, header stripping is your problem. Remux the video without header compression and it will play on your TV perfectly
Edit 2 : Here is how you can do it : http://wiki.serviio.org/doku.php?id=header_com