Making a recursive directory scan is easy, you just have to use File::Find, which is part of Perl's standard distribution.

A few points about my code: I use tr// instead of s/// as its more efficient when working on single character substitutions (or transliterations, to be precise). Also you should check if the target file already exists before attempting the rename... and always check system calls for errors.

#! /usr/bin/perl -w

use strict;
use File::Find;

my $root = shift || '.';

find( sub
    {
      return unless /\.mp3$/ and /[ ']/;

      (my $new = $_) =~ tr/ '/__/;

      if( -e $new ) {
          warn "Can't rename $_ to $new (latter already exists).\n";
      }
      else {
          rename $_, $new or warn "Could not rename $_ to $new: $!\n";
      }
    },
    $root );
[download]

g r i n d e r