I now have located the problem. After I updated WP to 3.4.1 all my categories when visited returned 404 Page Not Found results. After many hours trying to figure it out, together with my host, it finally seems that every time I activate WordPress SEO the error occurs. Without it it works fine. Real bummer as I was a big fan of the plugin. Any suggestion how I can get this to work again?