The patched code seemed to fix the problem. Please review ;-)
Problem was with nodes having terms without menu items if you choose term selection method "First term with menu" or "Last term with menu".
Thanks for your patch, it is committed to CVS now and will be included in the next release (6.x-1.1) in a few days.
Automatically closed -- issue fixed for 2 weeks with no activity.
Drupal is a registered trademark of Dries Buytaert.