First, let's get a picture of how your cabling situation is. Which cables are connecting your cable box, Slingbox, and TV? I suspect it's the issue described in this article:
Let us know if this article helps, and if it doesn't, let us know how your cables are hooked up.
Hope this helps!
From the sounds of it, it almost sounds like you're dealing with SOC, which is Selectable Output Control. This would only happen if there was an HDMI cable plugged in running out of your cable box, not necessarily to the Slingbox but in general. Do you happen to have one of these installed? It's also possible that the new set top box the Slingbox is connected to is running 1080p in 60 frames per second. If this is the case, you would need to have the cable box settings changed to 1080i or 1080p with 30 frames per second.
Please let me know if this helps!