Same thing is happening to me on a TiVo premier. It is very frustrating. On demand works fine from the Cox contour box I have, but not on the TiVo with a cable card &tuning adapter.
Update: My issue was resolved via a service tech visit. The tech was not even informed by Cox during his weekly training meetings that TiVo could do On-Demand, however he was able to talk to the BackOffice folks and get things sorted. In my case, the OD4TIVO code was already on my account. Neither he nor I are exactly sure what the issue was, however we suspect it was due to my cable card not being paired properly. I’d suggest starting with that if anyone else has a similar issue.