The concept of "git bisect" is inherently predicated on a simple linear history consisting of commits that were applied on top of each other. We are searching for the bad one which flips the test case from "good" to "bad".
If you throw an ugly graph into it and merges, it's not even comprehensible. Say that instead of git bisect we just go backwards, commit by commit, starting at HEAD. Oops, we encounter a merge commit: which way do we go now to find the breakage? Parent[0], or parent[1]? Or [2] ...? What is the correct traversal order? Do we go down [0] first? At which commit do we backtrack and try going into [1]?
There is absolutely no issue with git bisect over a repository where you have the unmodified upstream commits, and your own local ones rebased on top of them. It nicely finds the bad commit in one or the other.
Now of course the rebase rewrites your code by merging it (in the real sense of the word). If you discovered the bug yesterday (and it's in your own commits), then you rebased this morning, you're now chasing that bug over different commits that have been subject to auto-merge and maybe even manual conflict resolution. Oh well; yesterday was yesterday! Repro the bug with the newly rebased repo and bisect away.
Or, here is an idea: if you're chasing a bug, don't fetch anything and don't rebase! Right? If you've repro-d a bug, you don't want to start changing code, so the last thing you want is to bring in reams of changes from other developers. I've never rebased while chasing a bug with git bisect; I stopped what I was doing until I found it, in the nice linear history as it existed at that point.
If external forces cause you to drop what you're doing and rebase while you have some bug, what you can always do is "git tag bug-hunt" to set a bookmark where you were. Do what you have to do, and then when you pop your stack, return to that tag and debug from there. You can find the original bad commit. If it's in your uncommitted work, you can cross-ref it to the latest rebase. (There is a chance it might not exist any more; e.g. upstream changes made some of your local code obsolete, so you threw them away in the rebase, and the problem was in those discarded changes.)