Not sure what went awry but it works fine for me.
In[165]:= Solve[{x^2 + y^2 + z^2 == 1, x + y == 1}, Modulus -> 2] Out[165]= {{x -> 0, y -> 1, z -> 0}, {x -> 1, y -> 0, z -> 0}}
