@ echo
I had previously used the Top Level Cats plugin but after the upgrade to 2.5 I started getting this warning on the page when displaying a 404.
Warning: Invalid argument supplied for foreach() in /wp-includes/query.php on line 683
Removing the plugin got rid of the warning. I’ve been using the Category Base Removal Plugin for a few days with no problems.
If you want to get rid of the 404 for your custom category base create a category with the same slug as your custom category base, make it the parent of all your other cats, and design a custom template for it in your theme.