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 tolal 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 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 making the curves into proper position.)