I have the same problem. Because of line 563 in wp-includes/links.php.
Changing
echo ' <li id="'.sanitize_title($cat['cat_name']).'"><h2>' . stripslashes($cat['cat_name']) . "</h2>\n\t
to
echo ' <li id="'.sanitize_title($cat['cat_name']).'">' . stripslashes($cat['cat_name']) . "\n\t
work fine (just by stripping <h2> and </h2>).
Regards,
Coshkun.