Just diff the two directories.

    $ ls a b
    a:
    1  2  3  4
    
    b:
    1  2  3
    
    # Yours:
    $ diff -u <(cd a && find . | sort) <(cd b && find . | sort)
    --- /dev/fd/63	2011-11-20 02:50:21.919072726 -0700
    +++ /dev/fd/62	2011-11-20 02:50:21.919072726 -0700
    @@ -2,4 +2,3 @@
     ./1
     ./2
     ./3
    -./4
    
    # Mine:
    $ diff -u a b
    diff -u a/1 b/1
    --- a/1	2011-11-20 02:43:57.073130007 -0700
    +++ b/1	2011-11-20 02:45:14.535912768 -0700
    @@ -1 +1 @@
    -1
    +11
    Only in a: 4

Maybe I'm missing something?