You've noted that at high velocities, a tiny change in velocity can cause a huge change in kinetic energy. And that means that the thrust due to burning fuel seems to be able to contribute an arbitrarily high amount of energy, possibly exceeding the chemical energy of the fuel itself.
The resolution is that all of this logic applies to the fuel too! When the fuel is exhausted, it loses much of its speed, so the kinetic energy of the fuel decreases a lot. The extra kinetic energy of the rocket comes from this extra contribution, which can be arbitrarily large.
Of course, the kinetic energy of the fuel didn't come from nowhere. If you don't use gravity wells, that energy came from the fuel you burned previously, which was used to speed up both the rocket and all the fuel inside it. So everything works out -- you don't get anything for free.
For those that want more detail, this is called the Oberth effect, and we can do a quick calculation to confirm it. Suppose the fuel is ejected from the rocket with relative velocity $u$, a mass $m$ of fuel is ejected, and the rest of the rocket has mass $M$. By conservation of momentum, the velocity of the rocket will increase by $(m/M) u$.
Now suppose the rocket initially has velocity $v$. The change in kinetic energy of the fuel is
$$\Delta K_{\text{fuel}} = \frac12 m (v-u)^2 - \frac12 mv^2 = \frac12 mu^2 - muv.$$
The change in kinetic energy of the rocket is
$$\Delta K_{\text{rocket}} = \frac12 M \left(v + \frac{m}{M} u \right)^2 - \frac12 M v^2 = \frac12 \frac{m^2}{M} u^2 + muv.$$
The sum of these two must be the total chemical energy released, which shouldn't depend on $v$. And indeed, the extra $muv$ term in $\Delta K_{\text{rocket}}$ is exactly canceled by the $-muv$ term in $\Delta K_{\text{fuel}}$.
Sometimes this problem is posed with a car instead of a rocket. To understand this case, note that cars only move forward because of friction forces with the ground; all that a car engine does is rotate the wheels to produce this friction force. In other words, while rockets go forward by pushing rocket fuel backwards, cars go forward by pushing the Earth backwards.
In a frame where the Earth is initially stationary, the energy associated with giving the Earth a tiny speed is negligible, because the Earth is heavy and energy is quadratic in speed. Once you switch to a frame where the Earth is moving, slowing the Earth down by the same amount harvests a huge amount of energy, again because energy is quadratic in speed. That's where the extra energy of the car comes from. More precisely, the same calculation as above goes through, but we need to replace the word "fuel" with "Earth".
The takeaway is that kinetic energy differs between frames, changes in kinetic energy differ between frames, and even the direction of energy transfer differs between frames. It all still works out, but you must be careful to include all contributions to the energy.
You can think of gravitational energy being stored in a system of bodies, not just one body or the other. When you apply force over a distance (work) to the ball, it is being stored in the system of "the ball and the Earth." We can capture the concept of this energy stored in the system by saying its "stored in the gravitational field," but at the very minimum we should say that it's stored in the system.
Similar issues show up in electrostatics. In electrostatics, potential energy is almost always between two bodies, not in one or the other. If you choose to think of it as being in one body or the other, you end up in some really peculiar paradoxes.
What makes this tricky to understand intuitively is that we have many cases where one object is so astonishingly massive compared to the other that we can often handwave away this system-wide thinking, and pretend that the ball is the thing that actually has the gravitational potential energy. This is similar to how electrical engineers assume there is such a thing as a "ground" and that it can sink infinite electrical energy (there's a glorious pile of issues like ground loops which are associated with faulty assumptions regarding grounds). However, in many reasonable environments, these simplifications (such as assuming the earth doesn't move in response to us jumping upwards) are effective, so we keep using them.
There are also theories regarding what gravity "is" in general relativity and quantum mechanics. If one wishes, one can pursue those and come to a deeper answer. However, I don't believe they are necessary for everyone to learn.
Best Answer
Cory, here's a different way of thinking about gravity assists that may help:
First is my short answer for readers in a hurry:
What is really going on is a giant game of pool, with fast-moving planets acting as massive cue balls that impart some of their energy when they whack into tiny spacecraft. Since you can't bounce a spacecraft directly off the surface of a planet, it instead is steered to rebound smoothly off the immense virtual trampoline that gravity creates behind the planet. This field slows down and reverses the relative backward motion of a spacecraft to give a net powerful forward thrust (or bounce) as the spacecraft loops around in a U-shaped path behind the planet.
Next is my original, more story-style long answer:
Imagine a planet like Venus as a giant, perfectly elastic (bouncy) rubber ball, and your spacecraft as a particularly tough steel ball. Next, drop your steel ball spacecraft from space in such a way that it will hit the side of Venus that is facing forward in its orbit around the Sun.
The spacecraft will speed up as it falls towards the surface of Venus, but after it bounces — perfectly and without any loss of energy in this imaginary scenario — it will similarly slow down as the same gravity resists its departure. Just as with an elastic ball that at first speeds up when dropped and then slows down after bouncing on the floor, there is no net free "gravity energy" from the interaction.
But wait a second... there is another factor!
Because the spacecraft was dropped in front of the orbital path of Venus, the planet will be moving towards the satellite at tremendous speed when the bounce happens at the surface.
Venus thus acts like an incredibly fast, unimaginably massive cue ball, imparting a huge boost in velocity to the spacecraft when the two hit. This is a real increase in speed and energy that has nothing to do with the transient faster-then-slower speed change due to gravity.
And just as a cue ball slows down when it transfers impact energy to another ball, there is no free energy lunch here either: Venus slows down when it speeds up the spacecraft. It's just that its massive size makes the decrease in the orbital speed of Venus immeasurably small in comparison.
By now you probably see where I'm heading with this idea: If only there were a real way to bounce a spacecraft off of a planet that is moving quickly around the Sun, you could speed it up tremendously by playing what amounts to a gigantic interplanetary game of space pool.
The shots in this game of pool would be very tricky to set up, and a single shot might take years to complete. But look at the benefits!
Even if you start out with a relatively slow (and thus for space travel, cheap) spacecraft launch, a good sequence of whacks by planetary (or moon!) cue balls would eventually get your spacecraft moving so fast that you could send it right out of the solar system.
But of course, you can't really bounce spacecraft off of planets in a perfectly elastic and energy conserving fashion, can you?
Actually... yes, you can, by using gravity!
Imagine again that you have placed a relatively slow-moving spacecraft somewhere in front of the orbital path of Venus. But this time instead of aiming it towards the front of Venus, where any real spacecraft would just burn up, you aim it a bit to the side so that it will pass just behind Venus.
If you aim it close enough and at just right angle, the gravity of Venus will snatch the spacecraft around into a U-shaped path. Venus won't capture it completely, but it can change its direction of motion by some large angle that can approach 180 degrees.
Now think about that. The spacecraft first moves towards the fast-approaching planet, interacts powerfully with it via gravity, and ends up moving in the opposite direction. If you look only at the start and end of the event, it looks just as if the spacecraft has bounced off of the planet!
And energetically speaking, that is exactly what happens in such events. Instead of storing the kinetic energy of the incoming spacecraft in crudely compressed matter (the rubber ball analogy), the gravity of Venus does all the needed conversions between kinetic and potential energy for you. As an added huge benefit, the gravitational version of a rebound works in a smooth, gentle fashion that permits even delicate spacecraft to survive the process.
Incidentally, it's worth noticing that the phrase "gravity assisted" is really referring only to the elastic bounce part of a larger, more interesting collision event.
The real game that is afoot is planetary pool, with the planets acting as hugely powerful cue balls that if used rightly can impart huge increases in speed to spacecraft passing near them. It is a tricky game that requires patience and phenomenal precision, but it is one that space agencies around the world have by now learned to use very well indeed.