So not long after I posted this I understood the problem: the command
git rebase master
takes all the commits from the current branch, all the way back until the first commit that branches from 2nd argument ie master, and rebases them onto master HEAD.
To clarify why this didn't work, let's add more commits to my original diagram:
/- b1 - b2
/- a1 - a2
m1 - m2 - m3
where commits that start with "m" are on master branch (so master HEAD is at m3), those starting with "a" are on the a branch (so a HEAD is commit a2), and similarly for "b" (so b HEAD is b2). My goal was to end up with this:
/- a1 - a2
m1 - m2 - m3
\- b1 - b2
and the commands I tried are basically equivalent to
git pull
git checkout b
git rebase master
Problem is that "until the first commit that branches from master" includes the commits on branch a, so git will try to rebase a1 - a2 - b1 - b2 onto HEAD of master which is m3. This sequence of commits is already rooted at m3, so git says correctly that there is nothing to do.
I had to do instead git rebase --onto master a which means "rebase current branch (which is b) onto master, but only after the HEAD commit of branch a", ie "rebase b1 - b2 onto m3".