Weird problem... took months to figure out because I'm a bit slow. All taxonomy pages were doing infinite redirect loops if you were logged in, and sending users to the login page if you were logged out. So it was totally broken. In the end the problem was the "demo" taxonomy view that gets packaged with the Views module. It was on (although it seemed without any modifications) and turning it off solved the issue. I spent a long time trying to figure out what was wrong with the view itself and eventually gave up.