Assuming that $M$, $N$, $M N$ and $M N^2$ are noncubes, for a random prime $p$, the probability that $p \equiv 1 \bmod 3$ and $M$ is a cube mod $p$ and $N$ is not a cube is $1/9$. Trying some random primes and checking as Igor Rivin describes is probably faster than trying to be clever.

Proof of the probability claim: The hypotheses imply that the splitting field of $\mathbb{Q}(\sqrt[3]{M}, \sqrt[3]{N})$ has Galois group $\mathbb{Z}/2 \ltimes (\mathbb{Z}/3)^2$. Here, writing $\zeta$ for a primitive cube root of unity, this group acts by
$$\pm 1 \ltimes (a,b) \ : \ (\zeta, \sqrt[3]{M}, \sqrt[3]{N}) \mapsto (\zeta^{\pm 1}, \zeta^a \sqrt[3]{M}, \zeta^b \sqrt[3]{N}).$$

Let $\epsilon_p \ltimes (a_p,b_p)$ be the (conjugacy class of) the frobenius at $p$. Then $p \equiv 1 \bmod 3$ if and only if $\epsilon_p=1$; the numbers $M$ and $N$ are a cubic residue and non-residue respectively if and only if $a_p=0$ and $b_p \neq 0$. By the Cebatarov density theorem, we see that the proportion of primes which obey these properties is $2/18 = 1/9$.