I have checked that "Hide from the recent discussions page." is unticked for the Categories that are failing to display in Recent Discussions.
I think someone had a similar problem, perhaps not.
Create a new category, delete the old category and when it prompts you - move all the discussions to new category.
see if that solves it.
I may not provide the completed solution you might desire, but I do try to provide honest suggestions to help you solve your issue.
Appears that worked, thanks!