We recently added a new SEO feature to include the category name in the url. What version of the cart are you running? Do you have any ambersands or any other non alpha or numeric characters in your category name.
Another customer reported a similar issue and he had ampersands in his category names we are creating a new field under category management called "category_url" so we dont run into this issue.
-Scott