My first move was to check the revision 3419. The revision was a 'close branch' commit on a named branch. Nothing special and that was confusing.
It took me a while to realize: the error means there is a branch with more than one head. Now it seems pretty obvious :)
The following command produced me a list of branches along with the number of heads:
hg heads -c | grep branch: | uniq -c | sort
It turned out, there was an old, closed branch with two heads. Each head was closed with a separate commit. The solution was to merge these heads and close the branch once again.
I hope this post might help in case someone else runs into this issue.