Recoloring bipartite graphs
The problem is NP-complete and is thus not likely to admit a polynomial time algorithm.   Below is a proof of the NP-completeness of the problem, shown by a reduction from 1-in-3-SAT.

Let $\phi$ be an instance of 1-IN-3-SAT, where we are given a 3-CNF-SAT formula
asked to find a satisfying assignment where each clause is satisfied by exactly
one literal.  Let $V(\phi)$ be the set of $n$ variables, and $C(\phi)$ be the
set of $m$ clauses.

We construct an instance $G = (A,B,E)$ with a budget of $b = n + m$ (the allowed
number of blue vertices).

For each variable $x \in V(\phi)$, construct two red vertices $v_x$ and
$v_{\overline{x}}$ in $A$ together with $b+1$ blue vertices in $B$ adjacent to
both of them.  This forces exactly one of $v_x$ or $v_{\overline{x}}$ to be
flipped.  We also end up with $n$ flipped "variable vertices", thus using the
first part of the budget.

Remark: $\{v_x, v_{\overline{x}} \mid x \in V(\phi)\}$ are the only vertices in
$A$.

For each clause, say $c = x \lor \overline{y} \lor z$, we create $b+1$ blue
vertices and three extra red vertices $v_{x \in c},v_{\overline{y} \in c},v_{z
\in c}$, all in $B$.  Let $v_x,v_{\overline{y}},v_z$ all be fully adjacent to
the $b+1$ blue vertices and connect $v_x$ to $v_{x \in c}$, $v_y$ to
$v_{\overline{y} \in c}$, and $v_z$ to $v_{z \in c}$.



Now, since each clause gadget has $b+1$ blue vertices, we know that either one
or three literals in that clause have been flipped.  Suppose that three have
been flipped for one of the clauses.  But then we use at least budget $n + m +
2$.

Suppose that $\phi$ is a yes instance with a 1-in-3 assignment $\alpha: V(\phi)
\to \{\top,\bot\}$.  Flip every vertex which corresponds to $\alpha$.  Since
every clause is satisfied by exactly one variable, for each clause there is now
one blue vertex, and for each variable, exactly one of them is blue, hence we
have $n + m = b$ blue vertices.