I upgraded a couple sites to 3.4.1 and my category pages started to give 404 Not Found errors. After some digging, turning off plugins and switching themes, I found that the WordPress SEO plugin option to "Strip the category base (usually /category/) from the category URL" was causing the problem.
When that is checked, I get the 404 errors on the category page. When it is not checked, it works properly.
So, while domain.com/category-slug used to work prior to 3.4.1, that results in a 404 error now. Turning off the option means the URL is domain.com/category/category-slug now, but at least a page comes up.