Let's say you're trying to figure out $$\gcd(-2 + 4i, 6 + 10i).$$ Obviously $2$ is a divisor of greater norm than $1 + i$, and that's the answer I came up with. But $2i$ is also a divisor and it has the same norm as $2$ (so do $-2$ and $-2i$, but it seems obvious to me why neither of those should be the answer).
I ran through the Euclidean algorithm with pencil and paper and got $2i$ as the answer, but I think I made some silly mistake somewhere along the way. I'll doublecheck my calculations.
How do you resolve this dilemma? Or is there any dilemma here at all?
Short answer: the $G$ in GCD means "greatest". There is no natural order on $\Bbb C$, so there is no greatest of two complex numbers.
Long answer: I assume that you are talking about Gaussian integers here. The gcd still exists in a way, but it is not unique any more: it is unique up to multiplication by a unit (a Gaussian integer of norm $1$). Therefore, "the" gcd of two Gaussian integers is a collection of four Gaussian integers. If one of them is a positive real number, this may be your "preferred" gcd, by choice/definition, for the only reason that it may seem natural. However, it may very well happen that none of them be a real number. In this case, your question can't even be raised.