HDMI is all digital, so the quality of the cable really has less of an bearing than you would think. Its like those $10 spdif optical cables that work just as well as those $300 ones. A REALLY shitty cable could cause problems, but since its digital, they would be pixeation, freezing, picture scrambling and such, not so much "noise" or weak picture types of problems you would get with analog.
I have read of numerous incompability problems between HDMI devices however, as like everything, every company seems to have its own interripation of a "standard".
For example, my Olevia LCD TV will not work with my DirecTv H20 reciever properly in HDMI mode, but it works fine with specific revisions of them.
I know the PS3 had a lot of issues at first, but some were fixed with the update Sony released.
Your TV could just have a shitty HDMI implmentation as well, It happens. check to see it IT can be firmware upgraded.