Dear Fellow,

You can't move $E$ (!), hence there is no contradiction with it having self-intersection -1.
Indeed, if you take a normal vector field along $E$, it will necessarily have degree -1 (i.e.
the total number of poles is one more than the total number of zeroes), or (equivalently),
the normal bundle to $E$ in the blown-up surface is $\mathcal O(-1)$.

[Added:]  Here is a version of the argument given in David Speyer's answer, which is rigorous modulo basic facts about intersection theory:

Choose two smooth very ample curves $C_1$ and $C_2$ passing through the point $P$ being blown-up in different tangent directions.  (We can construct these using hyperplane sections in some projective embedding, using Bertini; smoothness is just because I want $P$ to be a simple point on each of them.)  If the $C_i$ meet in $n$ points away from $P$, then
$C_1\cdot C_2  = n+1$.

Now pull-back the $C_i$ to curves $D_i$ in the blow-up.  We have
$D_1 \cdot D_2  = n + 1$.  Now because $C_i$ passes through $P$, each $D_i$ has the form
$D_i = D_i' + E,$ where $D_i'$ is the proper transform of $C_i$, and passes through $E$ in a single point (corresponding to the tangent direction along which $C_i$ passed through $P$).
Thus $D_1'\cdot D_2' = n$ (away from $P$, nothing has changed, but at $P$, we have separated
the curves $C_1$ and $C_2$ via our blow-up).  

Now compute $n+1 = D_1\cdot D_2 = D_1'\cdot D_2'  + D_1'\cdot E  + E\cdot D_2' + E\cdot E
= n + 1 + 1 + 
E\cdot E$, showing that $E\cdot E = -1$.  (As is often done, we compute the intersection of curves that we can't move into a proper intersection by adding enough extra stuff that we can compute the resulting intersection by moving the curves into proper position.)