I have a ready static implementation of SAT.
It's neat and clean and is just about 70 lines of code.
I can give it to you if you need it. It handles polygons, lines and points.
You'll have to figure out how to make it dynamic by yourself, though.
(I mean, not completely by yourself, there's plenty of info. and I can help out here and there, but I'm not gonna write it for you. xD)

Umm... You know how projection works, right? What I do there is to basically smash a polygon against an axis. I project every point using the dot product, and the result of the dot product is some value... Now, I find the minimum and maximum and that's the interval of the polygon on an axis. (The 'x' there is the minimum, the 'y' is the maximum. That's stupid, I know. )
And what the hell do we need the intervals for?
Well, we project both objects on the same axis, check if the intervals overlap. If they do, we go on and check the next axis. If they don't, the objects can't possibly intersect.
The axes we need to check are actually the normals of the objects.
For the sake of illustration, I chose a random axis in the picture.
You can see on the right that the intervals overlap on that axis, but they don't intersect, so there must be another axis on which they don't overlap.

{"name":"satgb8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/f\/4f0defde056eec6feb1c754cf233dea3.png","w":706,"h":269,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/f\/4f0defde056eec6feb1c754cf233dea3"}

[EDIT]

As for how dynamic SAT works...
Imagine a moving line checked against another line... You can draw lines between the old and new points of the line, and you get a quad, right?
If that quad intersects the other line, we have a collision forward in time!
So basically, it's just the same old, but with one extra axis to check: The velocity.

{"name":"dynfs9.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/2\/92000938028336e60ab953d375cf379a.png","w":273,"h":249,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/2\/92000938028336e60ab953d375cf379a"}

So why only one extra axis if we have a whole quad now to check?
Because every normal of every side of a polygon is an axis, but the normals of parallel sides are the same, so we have 3 new sides formed, but the 'v' segments are parallel so there's actually just one new axis to check for, and the other side is parallel to the original line.

I gotta go now. I'll be back later.
Good luck!

I'll try to make things clearer...
Note that in the following, every time I say "polygon", I mean a convex polygon, a line, or a point. The code I present here is simpler than what I have in my previous post, because this code only tells you whether there is an overlap, but gives no information about how to resolve it.
If you can figure this out, I'll write another short tutorial explaining how to get a the minimal translation vector that would separate the two objects after the overlap.

Let's suppose that we're dealing with overlaps in one dimension.
We have a single axis, and the "objects" are represented by intervals on this axis.
Each interval has a minimum and a maximum value.

Checking whether two intervals overlap is very straight-forward:
Two intervals overlap, unless one of the interval's minimum is bigger than the other's maximum.

int intervals_intersect(INTERVAL int0, INTERVAL int1)
{
 if(int0.min > int1.max || int1.min > int0.max)
  return 0;
 return 1;
}

Now, let's move on to two dimensions.
It's an obvious fact that if you can draw a line between two convex polygons, such that each polygon would end up on a different side of the line,
the line separates the two polygons and they can't possibly be overlapping.
If no such line exists, then the polygons are overlapping.

http://img520.imageshack.us/img520/9764/slgj7.png

So we can state our problem this way: Check every potential separating line: if the line checked separates the polygons, terminate the
test and declare the polygons as non-overlapping. If none of the potential separating lines actually separate the polygons, they overlap.
Obviously, there's an infinite amount of lines we could test, so the trick is chosing a finite set that would give us conclusive results.
We'll get back to that later.
So how do we actually check if a line separates two convex polygons?
There are plenty of ways to do that, but the one I will present will prove to be very useful later on:
We find the normal of the line we're testing, we normalize it and project both polygons on it.
To project an polygon on the normal, we take the dot product of that normal and every vertex of the polygon.
The result of the dot product would be a scalar value, and if we imagine the normal to be a 1D axis, then this value would represent each point's
location on this axis.
For each polygon, we find the minimum and maximum of the dot product results.
The extrema give us the polygon's interval on the axis.

.
If the two intervals of the projected polygons don't overlap, the line separates the polygons.

{"name":"seplinerj5.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/4\/84cdd11457f968e7f7146198b6e7ecfb.png","w":245,"h":229,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/4\/84cdd11457f968e7f7146198b6e7ecfb"}

It can be proven that while there's an infinite number of such lines we could test, we only need to test a handful:
We only need to take each side of each polygon as a potential separating line.
If we find one that separates the polygons, we terminate the test and declare the polygons as non-overlapping.
If none of the them separate the polygons, they overlap.

Damn. You didn't have to go through that much trouble, though I think you've just written a good SAT resource.

And did a good job, too! Yeah, all of those snippets make perfect sense now. Hang on, I'm going to go look at the rest...

I think the only stuff that I don't get at this point is involved with the projection, but I never got around to looking into how that stuff works.

Wikify it!

I have a feeling this is going to be a lot less clear...

To resolve an overlap between two polygons, what we need to do is to turn one of the potential separating lines we discussed earlier into a real separating line. To do so, we need to make sure that the intervals of the polygons on the normal of that line stop overlapping.
This can be done by translating one of the polygons a certain amount in the direction (or the opposite direction) of the normal.
We compute a translation vector: Its direction is the direction of the normal (or opposite to it), its length is the amount of interval overlap (the area the intervals share).

{"name":"resoverip8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/a\/3a352044bcb17bfa86fd0ea827deaa78.png","w":553,"h":208,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/a\/3a352044bcb17bfa86fd0ea827deaa78"}

Note that in the picture, the blue rectangle is penetrating the red one from the right, so we would push it in the direction of the normal, to the right.
If it was penetrating from the left, we could still push it all the way to the right, but the reasonable thing to do would be to push it in the opposite direction, to the left.
First thing, we need to update our 'intervals_intersect' function to return the amount of overlap:

int intervals_intersect(INTERVAL int0, INTERVAL int1, double *depth)
{
 double d0, d1;

 if(int0.min > int1.max || int1.min > int0.max)
  return 0;

 d0 = int0.max - int1.min;
 d1 = int1.max - int0.min;

 *depth = (d0 < d1) ? -d0 : d1;
 return 1;
}

Note that 'depth' could be either positive or be negative, with plus meaning "in the direction of the normal" and minus meaning "in the opposite direction".
We could chose any side of the any of the polygons to separate the two, but for each line, the amount of translation needed to separate the objects would be different. The reasonable choice would be the line with the shortest translation vector, or in other words, with the smallest amount of interval overlap.
(Note that since we're doing a static test (i.e., not taking velocities into account), sometimes it might not be the most correct solution,
but it should be satisfactory in most cases.)
Here, for example, we would translate the polygon horizontally, since the amount of overlap is smaller:
{"name":"resover2cb8.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/b\/3b4dc9dfbf4b045ca087b8f599477056.png","w":279,"h":205,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/b\/3b4dc9dfbf4b045ca087b8f599477056"}

So here's an updated version of the 'poly_intersection_test', which would not only tell us if the objects overlap, but also how much and in
what direction to push them so they stop overlapping.
This code finds the normal with the smallest interval overlap and the actual smallest amount of overlap, then creates a minimal translation vector by scaling the (normalized) normal by the overlap amount.

Note that you can apply the resulting translation vector is several ways.
You could make one polygon immovable (world geometry, for example) and apply all the translation to one of the polygons, or you could
push each polygon in an opposite direction with half of the translation distance.
You could use the mass ratio to figure how much translation to apply to which polygon.

You're welcome.

P.S.:
I've just finished coding the dynamic version of the algorithm.
Works like a charm for lines and polygons at any velocity and just a bit more complicated than the static test.
I'm a bit too lazy to explain how it works right now, but here's the code:

Sorry, Anomie, but it turns out to be totally not worth it.
Working out the contact points is a real pain in the butt and I'm pretty sure it's gonna be as slow as your original algorithm eventually.
Also, dynamic SAT wouldn't work right for you, because it assumes that all points of a given object are moving at the same velocity, but in your case, a line segment might rotate, so each point would move with a different velocity. (A work-around might be to just chose the greater velocity for the test, but I'm not sure how it would turn out.)

[EDIT]

Now that I think of it, your algorithm would suffer from the "points with different velocities" problem too.
And if you do only lines vs. lines, figuring out the contact points would be a matter of another line intersection test after the collision has been resolved...
Damn, there's just no good way to deal with this problem!
No wonder even the most complex modern computer games use spheres and boxes for collisions.

You guys draw nice colorful pictures. I love this thread.

Damn... It sounds like the dynamic SAT won't work if things can rotate, and even if I used full polygons, the standard static SAT can't be trusted unless I make my lines out of really thick rectangles... I know people have done this before me! Argh! I need to think more.

The 'two different velocities' thing? Unless it's a perfect square, I guess...but I know that people have made systems where everything is made of point-masses/springs. I guess the solution may really be to find a way to separate everything into convex polygons dynamically...but gawd. It seems so ridiculous that the whole thing was made so much more complicated by gravity. It looks like 95% of the code in this system is going to be for the collision stuff.

[edit] As in...having even my lines made of tiny circles? Huh... I guess, if I really wanted to, I could move things at a fifth their normal speed, and do five times as many ticks per second, to try and avoid missing collisions due to high speeds... Could that really work?

[edit2] Wait, how would that be different from a simple distance-to-line check?

Oooooooh, I see! That makes more sense. So then... It still seems like I'd have to identify the shapes with enough accuracy to separate them into polygons...the hard part would be finding the center of a connected shape, with respect to the possibility of something like a box and a pole, attached by a rope of springs...which would each need to be registered separately for the circles, right?

[edit] I must just be real slow with my posting. If I do make my lines out of circles and test those, how's that different from the distance-to-line check?