Sorry, I only made this thread because I have *MY* solution and wanted to make it searchable for people. It seems like a lot of people have been having my problem. although few mention altering the wp-includes/rewrite.php file, all the symptoms and desired permalink structure are the same.
**** CAVEAT: I consider this a "hack." I altered core wordpress files to make my blog jump through my hoops. Following these instructions is done at your own risk, and may result in your blog, well, not blogging.*****
After searching all over these forums, I stumbled upon a link to a german blog (can't find the link now) that described a secondary change to rewrite.php. After removing "category/" from category_base, run a search for "// Put them together." (without the quotes).
There you will see a hierarchical breakdown of the rewrite rules. What is important to notice here is that $category_rewrite appears before author_rewrite, and subsequently, date_rewrite and post_rewrite. Simply moving $category_rewrite to the head of the link (i.e. search>author>date>post>category instead of search>category>author>date>post) made all my problems dissapear.
Hope this helps people. remember: this is a hack, and unless you know what you are doing, may result in your blog breaking.