I HATE spaces in file names
Bash 116 bytes, 16 spaces

find . -depth -exec bash -c 'B=${0##*/}
M="${0%/*}/${B// /_}"
while [ -e "$M" ]
do M=$M.
done
mv "$0" "$M"' {} \;


I didn't suppress errors to gain a couple more bytes. This will not have any collisions.

If non-posix GNU find can be expected, this can be shortened further:

Bash 110 bytes, 15 spaces

find -d -exec bash -c 'B=${0##*/}
M="${0%/*}/${B// /_}"
while [ -e "$M" ]
do M=$M.
done
mv "$0" "$M"' {} \;


Removing spaces instead of replacing them uses two less bytes:

Bash 108 bytes, 15 spaces

find -d -exec bash -c 'B=${0##*/}
M="${0%/*}/${B// }"
while [ -e "$M" ]
do M=$M.
done
mv "$0" "$M"' {} \;


Note: if tabs can be used instead of spaces, only 1 space is needed (the one in the match rule for substitution at line 2).

Thanks to Dennis for finding bug on double quote (and providing solution)