Just to summarize my understanding: First of all, the documentation states that Simplify assumes that variables are real when they occur algebraically in inequalities. Clearly, there are no inequalities in the logical expression y == 0 && x^2 == -1, and therefore x and y should be assumed to be general complex numbers. If they were real, then the simplification to False would be justified, because -1 has no real square roots.
When an expression can evaluate to True or False for different generic values of the variables, consistent with the assumptions, Simplify should leave it unevaluated. This is the case here if x and y are complex.
It therefore appears that the presence of And in the expression erroneously triggers the assumption of reality. The same happens when Or is present, as seen here:
Simplify[y == 0 || x^2 == -1]
(* ==> y == 0 *)
This simplification is only correct if one assumes x to be real so that the second clause is False. To see this, look at the result of Refine instead:
Refine[y == 0 || x^2 == -1, x ∈ Reals]
(* ==> y == 0 *)
The documentation states that Refine is one of the transformations called by Simplify. But without the assumption above, we get the correct result
Refine[y == 0 || x^2 == -1]
(* ==> y == 0 || x^2 == -1 *)
This means that before calling Refine, there is some processing inside Simplify that amounts to adding the assumption x ∈ Reals.
Whatever this additional processing is, it was absent in version 5.2 and is present in versions 8 and above. This fact leads me to conclude that it's a bug.
Also: the bug can't be removed by explicitly stating the assumption of complex variables:
Simplify[y == 0 || x^2 == -1, x ∈ Complexes]
(* ==> y == 0 *)