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.