Category Association Broken

Hello all,
I am troubleshooting a WP 3.0 instal for a client. He is experiencing an issue where, after turning on the Category Order Plugin http://wpguy.com/plugins/category-order/, he has now lost some the association between his posts and the categories.

The weird part is that the number of categories still shows in the dashboard, as well as the “most popular” category section on the side of the post-edit page. I have checked the database and verified that the categories and category associations are there. I am wondering if anyone has encountered a similar problem or any ideas on how to fix it? I told him its most likely a candidate for a wordpress re-install, but I would like to avoid that if possible.

Thanks!