One last thing to check is the access levels of the article's section and category.

All of my sections and categories are Public Access.

I suggest a fresh install, as was suggested earlier in the post. The only thing I can think of is that there is another extension controlling user access.

Any time you install, upgrade or delete other plugins and extensions, it's recommended that you backup both your database and your Joomla installation... something I sometimes forget and regret myself.

If you have a backup of the site and database when it was working, you can restore it and try to narrow down what changed from there.