My first impulse would be to say that you have a defective video encoder.
But you've already replaced the Xbox.
The MS AV packs work on the newer machines just fine (I have no such problem with a new unit).
So it is likely that you either have an impedance issue occuring between the Xbox and HDTV, or the HDTV's input stages are to blame.
That is unless someone at the place you got the XBox was consistently blowing the machines by hooking them up to something...
This begs the obvious question, was the box totally sealed?
Did it have both the top and bottom round seals in place when you got both boxes?
That said, there is indeed a slight difference in the newer Xboxes.
This has affected some devices such as the X2VGA which had to rewire the connector to overcome this problem.
(on the X2VGA this problem shows up as "wrong" colors however, not bars.).
If the bars are stationary, it's very hard to tell what's up.
If they vary depending upon what you are viewing/doing, it's quite possibly noise, ringing, interference, or impedance mismatch.
For yuks try changing out those monster cables for cheaper ones.
There was a similiar report (but not quite verticle bars) a few weeks ago that was cured this way. They too had monster cables!