The following should do what you want I think.
#!/bin/sh
OLD_DIR=old
NEW_DIR=new
# Make list of files, stripping off first directory in path
find "$OLD_DIR" -type f -print | cut -d/ -f2- | sort > files-old
find "$NEW_DIR" -type f -print | cut -d/ -f2- | sort > files-new
# Get files that are common
comm -1 -2 files-old files-new > files-common
# Create list of files to diff
sed "s/^/$OLD_DIR\//" files-common > files-to-diff-old
sed "s/^/$NEW_DIR\//" files-common > files-to-diff-new
# Do the diff
paste -d ' ' files-to-diff-old files-to-diff-new | xargs -n 2 diff -u
# Cleanup. Temp file handling should probably be done better by using
# mktemp to generate file names and using trap to make sure the files
# always are deleted etc.
rm -f files-common files-new files-old files-to-diff-new files-to-diff-old
It is just a simple, straight forward approach using several temporarily files. You might get away with some of those if you want to.