After some debugging, I found that a bug was introduced in a recent version of Data::Dumper (i.e. after 2.121_04 / perl 5.8.7, but no later than 2.121_08 / perl 5.8.8). Fortunately, the workaround is easy: Call Data::Dumper::init_refaddr_format() before calling Seen. It only needs to be called once, but it can safely be called multiple times.

use Data::Dumper ();

my $foo = [1..5];
my $bar = [ [6..10], $foo ];

Data::Dumper::init_refaddr_format()              # Workaround
   if *Data::Dumper::init_refaddr_format{CODE};  # Backwards compat

my $d = Data::Dumper->new([ $bar ], [ '$bar' ]);
$d->Seen({ '$foo' => $foo });
print $d->Dump();
[download]

$bar = [
         [
           6,
           7,
           8,
           9,
           10
         ],
         $foo
       ];
[download]

Update: This bug has been submitted as rt.cpan.org ticket 22766.