You get the cable box for the new system BEFORE they switch the old system off, or else you wouldn't have service until you got a new box. That's why you saw behavior change with the new box.
It simply isn't possible to send all the channels to customers at all times. There isn't enough bandwidth. So, the cable box at your house negotiates with the central or regional system so only a subset of channels are sent to you. There is no other way to do it in digital cable systems, and the switch to digital was made because it uses significantly less bandwidth than analog.
Right now I would be satifsied with at least some caching of the menus, so it doesn't have to pull the data every damn time I scroll up or down. Come on, it should be able to remember what channels I have for more than 5 minutes in a row.
You didn't think a cable company was going to deal with it's customers fairly, did you?
Every time you interact with a customer, there is an opportunity for profit. Telecommunications companies, cable TV included, are masters at this type of behavior.