Here's a construction proof of a case where rebase and merge produce different results.  I assume this is the case they are talking about.  Edit: There is another case that can occur, when merging branches where the side branch to be rebased has-or-merged contains one commit that will be skipped (due to patch-ID matching) during a rebase, followed by a reversion of that commit (that will not be skipped).  See Changes to a file are not retained by merge, why?  If I have time later I will try to add a construction proof for that example as well.
The trick is that since rebase copies commits but omits merges, we need to drop a merge whose resolution is not simple composition of its predecessors.  For this merge to have had no conflicts, I think it must be an "evil merge", so this is what I put into the script.
The graph we build looks like this:
  B   <-- master
 /
A--C--E   <-- branch
 \   /
  \ /
   D   <-- br2
If you are on master (your tip commit is B) and you git merge branch, this combines the changes from diffing A-vs-B with those from diffing A-vs-E.  The resulting graph is:
  B-----F   <-- master
 /     /
A--C--E   <-- branch
 \   /
  \ /
   D   <-- br2
and the contents of commit F are determined by those of A, B, and E.
If you are on branch (your tip commit is E) and you git rebase master, this copies commits C and D, in some order (it's not clear which).  It completely omits commit E.  The resulting graph is:
  B   <-- master
 / \
A   C'-D'   <-- branch
 \
  D   <-- br2
(the original C and E are only available through reflogs and ORIG_HEAD).  Moving master in a fast-forward fashion, the tip of master becomes commit D'.  The contents of commit D' are determined by adding the changes extracted from C and D to B.
Since we used an "evil merge" to make changes in E that appear in neither C nor D, those changes vanish.
Here is the script that creates the problem (note, it makes a temporary directory tt that it leaves in the current directory).
#! /bin/sh
fatal() {
    echo fatal: "$@" 1>&2; exit 1
}
[ -e tt ] && fatal tt already exists
mkdir tt && cd tt && git init -q || fatal failed to create tt repo
echo README > README && git add README && git commit -q -m A || fatal A
git branch branch || fatal unable to make branch
echo for master > bfile && git add bfile && git commit -q -m B || fatal B
git checkout -q -b br2 branch || fatal checkout -b br2 branch
echo file for C > cfile && git add cfile && git commit -q -m C || fatal C
git checkout -q branch || fatal checkout branch
echo file for D > dfile && git add dfile && git commit -q -m D || fatal D
git merge -q --no-commit br2 && git rm -q -f cfile && git commit -q -m E ||
    fatal E
git branch -D br2
git checkout -q master || fatal checkout master
echo merging branch
git merge --no-edit branch || fatal merge failed
echo result is: *
echo removing merge, replacing with rebase of branch onto master
git reset -q --hard HEAD^ || fatal reset failed
git checkout -q branch || fatal switch back to master failed
git rebase master || fatal rebase failed
echo result is: *
echo removing rebase as well so you can poke around
git reset --hard ORIG_HEAD