I don’t have multiple categories for the posts in question.
As a test, I just created a new category, created a post with that category, and changed the theme settings to exclude that single category. No luck: http://aboutonesouth.com/everything-we-do
Sooooo, I went on a plugin compatibility hunt. Turns out that we had a plugin called ‘ultimate category excluder’. It shouldn’t have created a conflict, but apparently does. Mystery solved!
Thanks for your help!