If you have zsh:
autoload zmv
zmv -QW '**/Old(/)' '**/New'
zmv -W '**/Old' '**/New'
Here autoload zmv loads zmv script that comes with zsh; zmv -W pattern replacement means «for each match remember value of all wildcards in pattern and replace corresponding wildcard characters in replacement with this value»; zmv -Q means «allow glob qualifiers in pattern»; '**/Old' means «match all files named «Old» in the tree under current directory» and (/) glob qualifier restricts «all files» to be only directories. Other useful zmv options:
-n: do not do anything, just print what will be done.
-i: show each line to be executed and ask whether to execute it
-f: force overwriting of destination files
If you prefer [ba]sh:
RnAll() { for f in "$1"/* ; do [ -d "$f" ] || continue ; ( RnAll "$f" "$2" "$3" ) ; [ "`basename $f`" \== "$2" ] && mv "$f" "`dirname $f`/$3" ; done }
RnAll . Old New
This is almost pure sh (or at least bash) solution, that does not require anything but shell and coreutils.