Now as to why the bug was stupid.
Data::Compare keeps track of how deeply recursed it is, so that it can yell at you if you try to compare stupidly deep structures. This is mostly so I can pre-empt perl's own warning about this, but I also think it's a good thing in its own right. To do this, whenever the Compare function is called, it increments a counter. This counter is passed to recursive invocations of Compare in a hashref.
As is good practice, as soon as my subroutine starts, I make my own local copy of all the parameters that are passed to it, eg
my $foo = shift;, so that any changes are localised. So I never bothered decrementing the counter, expecting the previous value to re-appear on exit from each subroutine. Trouble is, I was making my own local copy of a reference, and not a local copy of a value. So I was getting bitten by pass-by-reference vs the effective pass-by-value you get by making local copies of your parameters.
This is especially embarrassing because one of the talks I've given (at a Linuxbierwanderung) is entitled Perl Gotchas. In which I mention pass-by-reference vs pass-by-value. Doh!