For a spacecraft orbiting a planet, orbital speed is inversely proportional to orbit radius. But speed must be increased to increase orbit radius? For a spacecraft in orbit with radius $r$ with speed $v$ around a planet, centripetal force $F_C$ is provided by gravity:
$$\frac{GmM}{r^2}=\frac{mv^2}{r},$$
which simplifies to
$$\frac{GM}{r}=v^2.$$
This means that orbits closer to the planet are required to have greater speeds. However, if we want to move a spacecraft to a higher orbit, we have to increase the semimajor axis (adding energy to the orbit) by increasing velocity (source: FAA). How is this reconciled with the above equation?
 A: In a circular orbit, the total energy (with the standard choice of $U \to 0$ at $\infty$) is given by
$$E = T+U = \frac{1}{2}mv^2 - \frac{GMm}{r} = \frac{GMm}{2r} - \frac{GMm}{r} = -\frac{GMm}{2r}$$
Hence, as $r$ increases, the total energy also increases. It is true that the kinetic energy associated to a circular orbit decreases as one increases $r$, but the gravitational potential energy increases by twice as much, so that the total energy of the circular orbit increases. This is where one's added energy ultimately goes.
How does this happen, given that you must initially add this energy in the form of kinetic energy via boosters? It's simply that once you've done this and are moving radially outwards toward the higher radius, gravity is doing negative work because it is acting opposite to the radial component of your motion, i.e. the kinetic energy you added is being translated into gravitational potential energy.
A: The equation you have written there applies only for circular orbit but the orbit is not circular during the time the spacecraft is climbing to higher orbit. As the spacecraft climbs towards the higher orbit its initially increased velocity slows down as kinetic energy is transformed to potential energy.
A: A simple way to calculate moving from one circular orbit to a larger one:  Start by increasing the speed.  The orbit becomes an ellipse. As Kirby points out, the speed decreases as the satellite moves out. At the far side of the ellipse, increase the speed again to put the satellite into a larger circle. (Calculate using conservation of energy and angular momentum.)
A: If you are in a circular orbit at radius $r_1$ and want to move to a higher circular orbit at radius $r_2$, then you're right; your speed in the $r_2$ orbit will be lower than the $r_1$ orbit. So at some point in your transition to the new orbit you need to lose speed.
However, you cannot just magically teleport out to $r_2$ and then slow down. And if you slow down first (at $r_1$), you will then be going too slow for a circular orbit at your current position, so you will fall lower, not rise to $r_2$ (the resulting trajectory will be an elliptical orbit with highest point at $r_1$). So the only other thing you can do to try to get to $r_2$ is to speed up.
If you speed up from a circular orbit at $r_1$, you will then be travelling faster than the circular orbit speed at $r_1$. Gravity won't be able to bend your trajectory "fast enough" to stay at the same radius; your new trajectory will take you higher. That's what we want. If you calculate the amount to speed up just right, you can get an ellipse just touching $r_2$ at its highest point and $r_1$ at its lowest point, on opposite ends of the ellipse.
In an elliptical orbit, unlike the special case of a circular orbit, your speed is not constant; gravity speeds you up and slows you down over the course of an orbital period. Another way to look at this is that your total energy remains fixed (if you don't fire your engines to change speed), but your gravitational potential energy is higher when you are near the high end of your orbit, leaving less of your total energy that can be taken up by kinetic energy. Hence your orbital speed must be lower near the high end of the ellipse than it is near the low end.
When you are at $r_1$ you are travelling too fast for a circular orbit (that's why you rise to $r_2$ on the other side of the orbit). And when you are at $r_2$ you are travelling too slow for a circular orbit (that's why you fall back to $r_1$ over the other side of the orbit). So if you wait until you are exactly at the highest point of the ellipse, you can then speed up until you reach the circular orbit speed at $r_2$.
So (by this simple set of manoeuvres) you actually fire your engines twice in order to transition to a circular orbit at $r_2$, and both times you're firing to speed up. However in between the two burns you are coasting on an elliptical path on which you gradually lose speed; you lose so much that even after increasing speed twice your speed will still be lower than it was when you were originally travelling in a circular orbit at $r_1$.
So you see there is no contradiction between higher circular orbits being slower and needing to speed up change your trajectory to reach a higher orbit. You were forgetting about the intermediate ellipse connecting the two orbits, where you also lose speed.
