How 'bout something like the following (granted it can probably be improved upon:

use strict;
use warnings;
use Text::Wrap;

$Text::Wrap::columns = 80;

output (q|\e[33mCoruscate\e[0m;\e[37;40m is having trouble with a scri
+pt he is working on and therefore makes a trip to \e[32mwww.perlmonks
+.org\e[0m;\e[37;40m to seek help|);

# Modified print()
sub output {
 my $text = shift;
 my @removed;
 my $current_position = 0;
 while ( $text =~ m!(\\e\[[\d;]+[mK];?)!g ) {
  push @removed, [pos($text) - length($1), $1];
 }

 $text =~ s!\\e\[[\d;]+[mK];?!!g;
 my $wrapped = wrap('', '', $text);

 while ( @removed ) {
  my $current_element = shift @removed;
  substr($wrapped,@{$current_element}[0]) = @{$current_element}[1] 
    . substr($wrapped,@{$current_element}[0]);
 }
 print $wrapped;
}
[download]

update:did I mention it could be improved upon. I realized what hv noticed about 20 min after I left for lunch. I admit this code is therefore pretty broken. Thanks hv for the heads up anyhow.

update2: As for tye's solution above WOW!! I tried to fix my mistakes, but after figuring out how his worked I was humbled (need I say more).

-enlil