Warning, untested code...

how about something like:

my $dir = '/my/mp3/directory';
opendir(DIR,$dir) or die "Cannot open $dir: $!";
while(defined($subdir = readdir(DIR))) {
  next if $subdir =~ /^\./;
  next unless -d "$dir/$subdir"; 
  opendir(DIR2,"$dir/$subdir") or die "Cannot open $dir/subdir: $!";
  while (defined($file = readdir(DIR2))) {
     next unless $file =~ /\.mp3$/i;
     my $src = "$dir/$subdir/$file";
     my $dest = "$dir/$subdir/${subdir}_$file";
     print "renaming $src => $dest\n";
     # rename $src, $dest;
  }
}
[download]

-Blake