Is there a problem with Thunderbolt to HDMI in Lion?
The best chance of success (and Lion doesn't seem to affect this either way) is to have the cord connected when the TV is turned on. This lets the mac and the TV negotiate the formats that the TV supports. Sometimes hot plugging it, even though it's supposed to work causes interference (snow) or worse on the TV until you make the connection again.