Complex numbers are similar to vectors, but have some extra mathematical properties that make them useful. Most notably, using the complex exponential \$e^{j\omega t}\$ instead of sines and cosines makes differential equations much easier to deal with. That's how you get to complex impedance in the first place:
$$v(t) = A\mathrm e^{\mathrm{j} (\omega t + \theta)}$$
$$i(t) = B \mathrm e^{\mathrm j (\omega t + \phi)}$$
$$\frac {v(t)} {i(t)} = Z = \frac A B \mathrm e ^ {\mathrm j (\theta - \phi)}$$
Or, in phasor notation:
$$\hat V = A\angle \theta$$
$$\hat I = B\angle \phi$$
$$\frac {\hat V} {\hat I} = Z = \frac A B \angle (\theta - \phi)$$
You could use something like vector notation for the magnitude and phase, but vectors don't multiply and divide like complex numbers do, so it wouldn't improve anything.
EDIT: Complex numbers developed to solve certain algebra problems. If you want to know more about the history, check out the first chapter of Visual Complex Analysis by Tristan Needham. (You can read the preview on Amazon if you don't have a good library handy.)
The second chapter of the book can probably answer your question by itself, but I'll give it a shot too. Complex numbers are, in a sense, two-dimensional quantities, but what makes them useful here is that they also include the concept of rotation. Multiplication by \$\sqrt{-1}\$ is equivalent to a 90° rotation in a 2D plane:
$$\mathrm i ^ 0 = 1$$
$$\mathrm i ^ 1 = \mathrm i$$
$$\mathrm i ^ 2 = -1$$
$$\mathrm i ^ 3 = -\mathrm i$$
$$\mathrm i ^ 4 = 1$$
We can expand on this with complex exponentials, with let us represent a rotation by any amount:
$$\mathrm e^{j\pi/4} \cdot\mathrm e^{j\pi/4} = \mathrm e^{j(\pi/4 + \pi/4)} = \mathrm e ^ {j\pi/2} = \mathrm i$$
$$45^\circ + 45^\circ = 90^\circ$$
Notice that we get this by doing normal arithmetic -- multiplying real-valued exponentials works the same way.
Why does that matter? We can already represent rotations with sines and cosines, right? But that gets nasty in differential equations, mainly because you can't combine sines and cosines by adding them. On the other hand, the derivative of \$\mathrm e^x\$ is... itself. No trouble there!
So where does impedance come in? Well, think about the difference between DC and the sinusoidal steady state. At DC, node voltages are constant values with different magnitudes. At AC, node voltages are sinusoidal with the same frequency but different magnitudes and phase angles. The voltage/current relationships change too. With a resistor, voltage and current are in phase. In an inductor or a capacitor, there's a 90° phase difference between them.
So now the concept of rotation (phase "angle") has crept into our circuit analysis. We could stay in the time domain and do stuff like this:
$$v = L \frac {\mathrm d i} {\mathrm d t}$$
$$V\cos(\omega t) = \omega L\cdot I\cos(\omega t - 90^\circ)$$
Or we use could complex numbers, where a \$90^\circ\$ rotation just means multiplying by i (well, \$j\$ in our case -- this is EE):
$$V\mathrm e^{\mathrm j \omega t} = \mathrm j\omega L \cdot I \mathrm e^{\mathrm j \omega t}$$
The key benefit here is that all of the \$\mathrm e^{\mathrm j \omega t}\$ terms cancel out of equations, so now our voltage/current relationship is just Ohm's Law with complex numbers:
$$\hat V = \mathrm j \omega L \hat I$$
If I had to sum all this up in one sentence, I would say that complex numbers let you represent rotation by grouping the magnitude and phase together separate from the frequency, while sinusoids group the frequency and phase together.