threadsとuse utf8やuse encoding "utf8"は同時には扱えないのでしょうか?
例外処理でPerlそのものが落ちるようです。

#OS: WindowsXP SP3
#ActivePerl-5.12.2.1202-MSWin32-x86-293621

#!/usr/bin/perl -w
use encoding "utf8";
use threads;
my @threads;
for(1..5){
  #例外処理で落ちる
  my $thread = threads->new(\&my_thread, $_);
  push(@threads, $thread);
}
foreach(@threads){
  $_->join or die $!;
}
exit;

sub my_thread {
  threads->yield();
  sleep(1);
  return 1;
}