When was it realized that complex numbers can't lie on a number line? When I first learned about representation of a complex number by a point in a $2D$ plane, I wondered: what if it's redundant? What if a line is sufficient?
Apparently, it's not, but I still wonder: what is the proof of this? When was the fact first realized? Or was it totally obvious from the start of development of the theory of complex numbers?
 A: History
Complex numbers were introduced by Cardan (Girolamo Cardano) in his Ars Magna in 1545.
They were however described only purely algebraically as a means for solving  polynomial equations of degrees 3 or 4.
The first geometric description of $\mathbb C$ as points of a plane was given in 1799 by Wessel, a Danish cartographer, and independently by Argand, a Swiss-French bookshop owner, in 1806.
Argand was also the first to prove the "fundamental theorem of algebra" according to which  a real non constant polynomial has at least one complex root and he was the first to notice that the theorem also applies to polynomials with complex coefficients.   
Facts
The field $\mathbb C$ has dimension 2 (i.e. is a plane) as a real vector space : this is an easy result.
It also has dimension 2 as a differential manifold, which is a bit harder to show.
It has dimension 2 as a  topological space: this is really hard since already the very notion of topological dimension is quite sophisticated.  
Conclusion
To sum up and answer one of your questions:
No it was definitely not "totally obvious from the start of development of the theory of complex numbers" that they have  dimension two.
