Perhaps you might want to attack this from the other end. Instead of deep-searching to find references to the class, just dynamically update the log class to point where you want, overriding only the critical methods:

package Log;

sub new { 
  my ($class) = shift;
  bless {}, $class;
}

sub write {
  print "write old\n";
}

sub open {
  print  "open old\n";
}

sub close {
  print "close old\n";
}
1;

package NewLog;

sub import {
  for my $sub (qw(new write open)) {
    no strict 'refs';
    *{'Log::'.$sub} = *{'NewLog::'.$sub};
  }
}

sub new { 
  my ($class) = shift;
  bless {}, $class;
}

sub write {
  print "write new\n";
}

sub open {
  print  "open new\n";
}
1;

use Log;
use NewLog;

my $log = new Log;
$log->open;
$log->write;
$log->close;
[download]

If you run this, you'll see the following output:

open new
write new
close old
[download]

Note that open and write are overridden, and close is not. This incurs less overhead if you've got a lot of Log objects, or if your objects using them are very deeply nested.