Here's another version... Seemed like a fun problem (I love recursion), so I hacked this up:

#!/usr/local/bin/perl -w

use strict;

sub dirs {
        my @retval;
        opendir DIR, ".";
        my @file = readdir DIR;
        closedir DIR;

        for (@file) {
                next if /^\.\.?$/ or -l $_;
                push @retval, $_ if -d $_;
        }

        return @retval;
}


sub rename_dirs {
        my $dir = shift;
        chdir $dir;
        my $newname;

        for (dirs()) {
                rename_dirs($_);
                if (/ /) {
                        ($newname = $_) =~ s/ /-/g;
                        rename $_, $newname;
                }
        }
        chdir "..";
}

rename_dirs($ARGV[0]);
[download]

Update: -l $_ added after receiving a comment by merlyn. thanks!