I sent this to Michael as well, but thought someone might see this and have an idea. I hope he'll forgive a bit of copy and editing from the question in my email.
It looks like publishing a post under a category breaks the permalink functionality (using 2.7).
In our case, we have a hierarchy of categories; e.g., 'meta - Hide quoted text -category', then under it 'sub category a', 'sub category b' and 'sub category c'. The intent being to use those as templating criteria. And it almost works, except that posts we make under the 'meta category' category show an odd issue.
Instead of redirecting to the correct post if one visits a permalink, instead it'll just show the most recent post under 'meta category'. So if I made three posts under the 'meta category', 'post 1', 'post 2' and 'post 3' in that order, it would load 'post 3' when I went to the permalinks of 'post 1' and 'post 2'.
The main issue, I suspect, is that we're using wordpress 2.7. But I was hoping someone might have some other ideas about what could be causing it.