Generating bilinear pairing parameters - running time of finding member of p-torsion group
In your step 2 replace $p$ by $p^2$. That should do it.

But you should really be looking for points Q on the sextic twist. See the original Barreto-Naehrig paper.