The issue is that you branched off a branch off of.... where you are trying to rebase to. You can't rebase to a branch that does not contain the commit your current branch was originally created on.
I got this when I first rebased a local branch X to a pushed one Y, then tried to rebase a branch (first created on X) to the pushed one Y.
Solved for me by rebasing to X.
I have no problem rebasing to remote branches (potentially not even checked out), provided my current branch stems from an ancestor of that branch.