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.