There is a bug in the code that generates solutions of triangular systems which affects cases that involve finding solutions of quadratics with complex coefficients. Should be fixed in the next release. As a workaround, you can disable the code by setting a couple of system options.

In[1]:= SetSystemOptions["ReduceOptions"->{                                   
           "UseNestedRoots"->False, "UseTriangularRoots"->False}];            

In[2]:= sys = {1 + x1^2, -3 + x2^2 + 4 x2*x1, -3 + x3 + x2*x1};               

In[3]:= sol = Solve[sys == 0]                                                 
Out[3]= {{x1 -> -I, x2 -> I, x3 -> 2}, {x1 -> -I, x2 -> 3 I, x3 -> 0}, 
>    {x1 -> I, x2 -> -I, x3 -> 2}, {x1 -> I, x2 -> -3 I, x3 -> 0}}

In[4]:= sys /. sol                                                            
Out[4]= {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}, {0, 0, 0}}

Thank you very much for the explanation!