Turned out it was some of our own code in lib/navigationlib.php that was causing the problem. The code was not marked with our standard "LOCAL HACK" comments, so we did not see it for several days. It's been taken out and the breadcrumb trail is working again.
No wonder I stumped the community. ;)