If $E$ has cubic twists, then it has CM by $\mathbb Q(\zeta_3)$. Let $\eta$ be the Hecke character of $\mathbb A_{\mathbb Q(\zeta_3)}^*$ associated to $E$. Then $f$ is the automorphic induction (i.e. theta lift) of $\eta$. Now, let $\chi\colon G_{\mathbb Q(\zeta_3)}\to\mathbb C^*$ be the character corresponding to the Galois extension $\mathbb Q(\sqrt[3]d, \zeta_3)/\mathbb Q(\zeta_3)$, and abusing notation, let $\chi$ also denote the corresponding Hecke character of $\mathbb A_{\mathbb Q(\zeta_3)}^*$. Then $f$ is the automorphic induction of the Hecke character $\eta\otimes\chi$.

@stupidboy These lecture notes might help. The point is that by extending from $\mathbb Q_p$ to a finite ramified extension, you add many new lattices in the Bruhat-Tits building in between all the lattices that you already had. Your question (when $n = 2$) is Exercise 1.10.

You can get a lot of intuition for what's going on just by looking at elliptic curves, using the dictionary between lattices in the $p$-adic Galois representation of $E$ and Tate modules of elliptic curves with a $p$-power isogeny to $E$. There, the analogue of your question is: if $E$ admits a cyclic $p$-isogeny, then is $E$ isogenous to some elliptic curve $E'$ that admits two independent $p$-isogenies? The answer is, of course, no, unless $E$ already has a cyclic $p^2$ isogeny.

So perhaps you can use an explicit version of the Chebotarev density theorem to get a bound for small $B$? On the other hand, when $B$ is too small, you have to contend with the Hasse bound $|p + 1-\#E(\mathbb F_p)| < 2\sqrt p$. If $\#E(\mathbb F_p) = a + bn$ for some $n\in\mathbb N$, then by the Hasse bound, $(\sqrt{a+bn}-1)^2 < p < (\sqrt{a+bn}+1)^2$. If you take $B\approx b^2$, then the largest $n$ can be is about $b$, and so maybe that gives an additional constraint?

Let $\rho_b\colon G_{\mathbb Q}\to \mathrm{GL}(E[b])\simeq \mathrm{GL}_2(\mathbb Z/b\mathbb Z)$ be the mod $b$ Galois representation arising from the action of $G_{\mathbb Q}$ on the $b$-torsion points of $E$. Then your set is exactly $\{p \le B : \det(1-\rho_b(\mathrm{Frob}_p)) = a\}$ (except for finitely many primes $p$ of bad reduction). Let $C(a, b) = \frac{\#\{g\in \mathrm{Im}(\rho_b) : \det(1-\rho_b(g)) = a\}}{\#\mathrm{Im}(\rho_b)}$. Then, by the Chebotarev density theorem, we have $\{p \le B : \det(1-\rho_b(\mathrm{Frob}_p)) = a\} \sim C(a, b)\frac{B}{\log B}$ as $B\to \infty$.

@JeffH I intended that to be more of a counterexample than an example, by replacing $\mathbb Q(\sqrt{-7})$ with $\mathbb Q(\sqrt{56})$. What makes this work is exactly the fact that $\mathrm{rk}\ E(\mathbb Q(\sqrt{56}) = 0$.

I think so. You can do all this without BSD. Let $\mathrm{Gal}(F/\mathbb Q)$ act on $V:= E(F)\otimes\mathbb C$. Then you can decompose $V$ as a direct sum $\oplus V_\chi$ over the isotypic components corresponding to the irreps of $G$. Some components will come from $G_1$ and $G_2$, but others will come from neither. It is these ones that you have to somehow control.

I think you have an extra factor of $L(E, \mathbb Q, s)$ in your factorisation. (e.g. it goes wrong if $F_1 = \mathbb Q$)

@ChrisWuthrich Is there a way to lift those automorphisms to $\overline{\mathbb Q}$ without AC? The usual argument uses Zorn's Lemma.

Shouldn't it just be something like $[K:\mathbb Q]/\#\mathrm{Aut}(K/\mathbb Q)$?

The representation $\rho$ factors through a finite Galois extension $\mathrm{Gal}(L_f/\mathbb Q)$. The field $L_f$ is unramified outside $Np$ and has degree at most $|\mathrm{GL}_2(\mathbb F)|$ (actually, it's a bit smaller - there are constraints coming from the determinant). So by Hermite-Minkowski, every Galois representation of this shape factors through some $\mathrm{Gal}(L/\mathbb Q)$ where now $L$ depends only on $N$, $p$ and the size of $\mathbb F$. All this can be made explicit, and now you can just apply standard Chebotarev estimates to the extension $L/\mathbb Q$.

When $p=2$, $K = \mathbb Q$, and $j(E_1)$ and $j(E_2)$ are not simultaneously $0$ or $1728$, then a positive answer follows form Theorem 4 of this paper.

I think this should be known (assuming of course that $f$ is not a theta lift, in which case it's false). Prop. 2.2 of the Fischman paper quotes Thm 15 this Serre paper. The only modular forms specific input of the proof is Prop 17, which requires knowing that the $l$-adic Galois representation $G_K \to \mathrm{GL}_2(\overline{\mathbb Q}_\ell)$ associated to $f$ is absolutely irreducible when restricted to any finite extension of $K$. But this is known for Bianchi modular forms.