I think the time I'm most likely to rebless an object is if I want to subclass an existing package to get some modified behaviour. Mostly in such cases I can simply inherit from the base class and Subclass->new will do the right thing, but in some cases the base class's new relies on the invoked class's name to create the right object.
My work application has occasionally needed such tricks, since the underlying database abstraction uses the class name to find the object-to-database mapping information. However as of now, there is only one example of such reblessing in 50 KLOC (and that in a proof of concept utility that won't be updated), since most of the original needs for it were removed when the database abstraction was modified to call the invoked class's bless method. We do have 6 examples of classes that overload bless to do various interesting things, and most of those would originally have reblessed the objects instead.
Hugo