Probably something like the following. Before running it, follow the link of (3) and run the script there.

#!/usr/bin/perl -w

use strict;
use File::Find;

my $dir = '.'; # or wherever

finddepth(\&myrename, $dir);

sub myrename {

    return unless -d; # if you only care about dirs
    return unless / /;
    my $oldname=$_;
    s/ /_/g;
    return if ($oldname eq $_);

        if (rename $oldname,$_) {
              print "renamed  $File::Find::name to $_\n";
        } else {
              warn "Couldn't rename $File::Find::name to $_: $!";
        }
}
[download]

Notes:
1. Adapted from 32038
2. PM is acting wierd today!
3. This was around before: rename directories recursively to remove spaces from names has a safer way.
4. Changed according to tye's suggestion