Suppose I have
$$ z=(a+ib)\implies z^2=(a+ib)^2\implies z=\pm(a+ib) $$
But if I do this instead:
$$ \begin{align} z&=a+bi\\ \implies z^2&=a^2-b^2+2iab\\ &=a(2a+2ib-a)-b^2\\ &=a(2z-a)-b^2\\ z^2-2az+a^2+b^2&=0\\ &\implies z=a\pm ib \end{align} $$
Why the contradiction?
There is no contradiction. In the first derivation, you have shown that if $z=a+ib$, then either $z=a+ib$ or $z=-a-ib$. That is true, because $z=a+ib$.
In the second, you have shown that if $z=a+ib$, then either $z=a+ib$ or $z=a-ib$. That is true, because $z=a+ib$.