Would have been dealt with even earlier, but our experiments with it (http://meta.stackoverflow.com/a/69032/130213) lead us to believe Google was starting to treat us as a link farm.
What we were seeing in our earlier attempt wasn't pages appearing lower in results (which could reasonably be expected in some cases as a result of the change; and we wouldn't care, 2nd on a search under an equally good resource is fine by us), but pages being removed entirely; almost universally pages that had newly un-nofollow-ed links to stores, or ad-laden sites (mostly legitimate posts, but some spam that stuck around for a bit before the community deleted it). So, "classified as link farm" seemed like the most likely problem. Google naturally won't tell you why your ranking drops, so it was (and remains) just an educated guess as to what happened.
So we stopped, putting it on the "wish we could, but reality doesn't let us"-list until Google reached out to us (among thousands of others, I'm sure) to change our nofollow practices. Google didn't describe any changes in their algorithm, but it seems reasonable to me that there would have been some tweaks around nofollow to accompany a new policy; again just an educated guess.
Basically, this is an old post complaining about a long since addressed concern that we had tried to address even earlier but ran into practical problems with.
While the exact details of our algorithm are secret by necessity, I will say that we've had to consider posts individually to prevent spammers from kiting a single account up to post nofollow-less spam content. People still try, it's kind of astounding how much spammers try (I suspect SEO's opaqueness cuts both ways here), but it doesn't work (well, you can get one link in your profile; but there's less SEO juice to pass and you are hard-capped at one, no matter how long it takes someone to delete your account).
Disclaimer: Stack Exchange employee, I was on all the relevant calls but has been a couple years so grain of salt and all that.
I'm not sure why this made HN 2 years after posting it, but I wanted to make a comment.
SO has implemented a way to remove the nofollow links, but it is way too strict, and probably only affects a very very very small percentage of answers. I'd bet less than 0.1%.
For example see this answer with 74 upvotes from a user with almost 100k reputation.
The links are to MSDN (which is probably not spam by definition) and to a quoted source on techbubbles.com.
I'll dig into it, should have a fix in the next deploy (assuming it is a bug, but I don't see what else it'd be).
So, either the algorithm is really strict and fairly capricious, or it's quite badly broken.
When Google is 90% of your traffic, you REALLY REALLY REALLY do not want to get on their bad side, even accidentally, so I can hope you understand why we wanted to be cautious to the extreme here. If Google decides you're not doing things right, it is literally a business ending move.
Unless your VCs and investors are cool with you losing, y'know, ninety percent of your traffic.
History seems to bear out that SO correctly identified the source of the "problem", and SO is such a valuable resource that I'd rather it be Google-visible over passing pagerank.
This is the problem when you have a single player dominating the search space with an opaque algo and a very limited appeals process.
The site still applies rel=nofollow to what seems like the majority of outgoing links. Since I would call the overwhelming majority of content on Stackoverflow not spam, there's a lot of good links getting nothing.