There have been a number of answers here that answer slightly different questions. As I understand it the question is "Why does the Coriolis force apply to objects (or air parcels) moving east and west, as well as those with a north/south component?"
It's a good question. The common intuitive explanation of the Coriolis effect, which you describe, considers only the horizontal forces acting on an object. That isn't quite right. This diagram adds two more forces that matter:
The arrow marked "g" is the force due to gravity, and is directed towards the centre of the planet.
The other arrow represents the centrifugal force that results from the earth's spin. Notice that it does not directly oppose gravity, but instead acts away from the earth's axis of rotation. In the absence of aerodynamics, buoyancy, etc, the vertical components of these forces must cancel out so that our particle maintains its altitude, but there is a resultant horizontal force towards the equator.
Let's assume that our red dot is stationary with respect to the earth's surface (the horizontal component of the centrifugal force must be balanced by something else). If the red dot accelerates to the east (away from us), meaning that its angular speed around the axis of rotation of the earth is increased, then the centrifugal force will increase, while the gravitational force will remain (very nearly) the same. Thus it's no longer in equilibrium. This has two effects: the vertical component of this is a force upwards which I believe is known as the Eötvös effect, and the horizontal component is a force towards the equator (a right turn in the northern hemisphere), which is Coriolis.
Similarly if the dot accelerates to the west (towards us), its angular speed decreases, the centrifugal force decreases, and it is pushed down and away from the equator (a right turn in the northern hemisphere).