menu > search > smart search > type "CLEARMYBOX" in the suggested searches field. Press the red button. Wait up to 15 seconds (usually much less) and it will completely reset, but it will keep your timers and personalized stuff (settings, fav list, etc). When it comes back, wait up to 2 days for everything to load. A good way to tell when it should be ready is when the channel logos appear in the info banner again. Then, you should try the On-Demand again.
Note: Do the CLEARMYBOX when you aren't recording anything and nothing is scheduled for about 6 hours. It can take that long for the scheduler thing to complete the to-do list.