This is my output from Deparse in both Perl 5.6.0 and 5.6.1

perl -MO=Deparse -pi.bak -e "s[^#!/usr/local/bin/perl][#!/usr/bin/perl
+]"
LINE: while (defined($_ = <ARGV>)) {
    s[^#!/usr/local/bin/perl][#!/usr/bin/perl];
}
continue {
    print $_;
}
-e syntax OK
[download]

There was no need for escaping the "!" and it worked fine (I searched perlre about the need for escaping the bang, but I couldn't find it. Did I miss something?).
So I couldn't replicate your error condition. Sorry.
However, I agree that your script is more readable. :)