One possibility is that the new TV (especially if it is a plasma) is emitting infrared light from the TV screen, and this is interferring with the IR sensor in the cable box.  Try shielding the IR sensor of the cable box so that only IR from the remote can get in.  Note that IR can reflect of walls, pictures, etc. so you may need to make a small funnel and aim the remote into the funnel.

If you can get good operation this way, then you can try something more permanent.  Sometimes just pasting a piece of paper over the cable box sensor will cut down the interference while still allowing the cable remote to function.