I am using WP 3.1 and the latest Classipress version. I have a multisite with 4 blogs with the same theme settings.
There are various phenomenon in the different blogs:
Blog 1: http://www.motortipp.net
I have posted a test ad. It's is visible under "just listed" at the very bottom of the site, but not under the respective category. clicking both the main category and the subcategory where the post was added you get to the error 404 site.
BUT: Blog 3: http://www.immotipp.net
no posts added yet, but clicking on main categories it correctly shows the listings and the subcategories in the sidebar.
Blog 4: http://www.anzeigentipp.net
I posted a test ad on the main category Computer, Büro. Clicking on the main category it correctly shows the listing plus ad, clicking on sub category you get the error 404. clicking on an empty main category it also works fine.
for Blog 3 and 4 see attachment screenshot 2