This is related to the fact that hg pull could lead to quite funny things 
when mq patches are applied. (Something like this was predicted in issue1099)

(The following scenario is the same as the attached test-pull-mq)
Let's suppose we have
 Repo1: a - b(p) - c(p)
where *(p) is an mq patch.
If we tried to commit over b it would fail and this is good. 

But if we had another repo:
 Repo2: a - b - d
with b == b(p)

A pull from repo1 would lead to:
 Repo1: a - b(p) - c(p)
             \
               d

Actually this is exactly what happened to the OP.
A pull --rebase in Repo1 means: hg pull && hg rebase -s c(p) -d d
In this case rebase tries to finalize c(p) but it fails.

From rebase's point of view we could finalize also b(p) and then c(p).
This solves the problem, but b(p) won't be an mq patch anymore.

If this is an acceptable behaviour see the attached patch to rebase.py
(rebase_qfinish.patch)
Please note that this requires to finalize every applied mq patch and then 
try to import it again.

Another approach could be finalizing b(p) after pull, but this has nothing 
to do with rebase.

Workaround:
qfinish the patch and continue the rebase (hg rebase -c)

I'm sorry, my "fix" to the patch wasn incorrect.  I didn't update the line count.

test-rebase-mq-skip_extend-patch_fixed_again.patch is the one you want.

There seems to be a problem with the patch attached by simohe.

$ hg import ../test-rebase-mq-skip_extend.patch
applying ../test-rebase-mq-skip_extend.patch
abort: malformed patch a/tests/test-rebase-mq-skip @@ -41,4 +46,33 @@

I am attaching a modified version that imports without complaining.

When a patch is applied remote in the same place as it is in the mq, then it is
not pulled because it is here, but its children are pulled. It is impossible to
qpop the patch. The only thing you can do is qfinish.
pull --rebase does not handle this situation. (I needed some time to fix the mq...)