I was able to accomplish what I needed to by noodling out Lanx's suggestion.

Ok, but note LanX's warning, which I agree with - B::Deparse is more of a debugging tool, and does not guarantee to be able to round-trip Perl code, so your solution will be quite brittle. Using a regex to replace the package name will blow up on something as simple as:

package Spin::Command::spin;
our $foo = "Bar";
sub func {
    print "Foo:$foo";
}
[download]

Because the deparse of func is:

{
    package Spin::Command::spin;
    print "Foo:$foo";
}
[download]

If, as you seem to be saying here, you really just want to replace run and don't need other replacements, then my suggestion, even though it's still kind of a hack, is much more robust (relative to it being a hack, at least).