I would recommend trying to change the resolution, or the cable itself. I know it seems like a strange difference, but if the cable isn't a HDMI v.1.3, then it may have problems with some cable boxes.
Also, you may check to see if your cable box has an update or needs to be refreshed to work with the new television. This can be done usually while you're on the phone with the cable/sat company.
I have a new UN40B7000 40-Inch 1080p LED HDTV which works fine w/component cables. When connecting HDMI, it reports "no connection".
The cable box is Comcast Motorola. I have similar setup w/a 52" LN52A850 which works great. I am on 2nd cable box and ruled out bad HDMI cable. Anything else to try?