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.