It could be that the TV only accepts 1080p via a digital signal (HDMI cables are more expensive to sell you than component). Not really sure, seems a bit odd to me.
If you say you got it on the old TV and not the new one using the same setup otherwise, odds are something about the new TV is now allowing it to go through as a progressive signal.
I don't know of a fix, but in any event I know its annoying, but if you're happy with the TV otherwise just take the 1080i and be happy. I know its not the best, but the difference is very small and not really noticeable unless you're looking for it.