Won't there be shared code that accesses internal data? Or code in one class that accesses data set by the other class?

If all accessors are defined in terms of low level operations then all you have to do is overload the low level operations and the highlevel ones are taken care of.

What are you gaining by re-blessing then? Sounds like you want to just read the data and make a new object.

Well if there are many references to a single object then going around and changing them all one by hand is tedius and error prone, and probably not even possible at all. On the other hand reblessing the object affects every reference to the blessed referent so its affect the lot of them in one go. Thats just one gain. Another gain could be what I was referring to in the part of my message you didnt comment on, where the object may have several possible internal representations and the class represents which state the object is in.

If these defined accessors are written to work with different internal structures, how can they work on the same data?

I have to say I dont get what you dont get here. This seems to me to be obvious stuff: Because you have supplied methods to do so. Just like with any other class.

package Any;
sub new { my $class=shift; bless {},$class }
sub name {
  my $self=shift;
  my $type=$self->type;
  $self->{$type}{name}=shift if @_;
  $self->{$type}{name};
}
sub mirror {
   my $self=shift;
   my $other=$self->other;
   my $type=$self->type;
   $self->{other}= delete $self->{type};
   bless $_[0],$other;
}
sub type { 'neither' };
sub other { 'Any' };

package Leftie;
@ISA=qw(Any);
sub type { 'left' };
sub other { 'Rightie' };
1;

package Rightie;
@ISA=qw(Any);
sub type { 'right' };
sub other { 'Leftie' }
1;
[download]

As you can see the two classes actually dont know anything about the others insides at all. Hell, the full behaviour is defined by Any.