I'm having the same issues on one Apple TV. I did a full reset/update/install on the one in my bedroom and it seems to be working, although I rarely use the Up Next. I have to open ATV App to get them to show and they're showing the last shows that I watched.
In the living room, I have to play a show that I've been watching and when I go back, all my Up Next shows are there. Hopefully this is fixed in the next update.