As a side note, I did a fresh install on a new server and the KB worked. I was able to create new categories and articles as well. Looked at a few tables and did not see much difference. Restored our database on the new server and the KB broke again. So this is clearly something on the database side that is not linked the articles to the categories some how.
I will try to dig into the tables to see if I can find any differences. Hopefully someone from Support can mention some script we need to run or that it will be in an update coming soon.