So when the constant is negative, iteration of $f=\sqrt{-a-x}$ converges quite easily. Also the derivative is less than 1 as long as $-2 \lt a \lt {1 \over 4}$, I don't think that's relevant as the iteration converges regardless of a.
If the constant is positive however the iteration doesn't seem to converge at all. For instance if $a=1$ and I start with $-0.5-0.5i$ I converge to $1/2+1.322...i$ rather than $-1/2-\sqrt{3}/2$. More surprisingly, the absolute value of the derivative at the fixed point is $1/2$, so the point should be attractive. What's going on here?
How do I set up the iteration so that it can converge properly to the complex root?
More generally, what kind of conditions do I need to set up for complex fixed point iteration? (Posted from mobile)
As Thomas Andrews pointed out, the issue is with the choice of branch of the square root. One should use the branch that is consistent with the equation near the root (of course, this is something that's not easy to do in general, if one doesn't know where the roots are). In this case, for $-1/2 - \sqrt{3}/2 i$ to satisfy $x = \sqrt{1-x}$ one needs the branch other than the principal one.
In general, it's wise to use a branch cut that lies as far from the expected roots as possible.