Adam Lasnik said on Google Groups:
…reciprocal links have been around forever, and Google doesn't frown on engaging in reciprocal linking in moderation.
The key here is, indeed, moderation . If, say, 90% of your backlinks are reciprocal, that's probably not going to improve how our algorithms view your site. Or worse, if 90% of your backlinks are reciprocal and not likely to be of interest to your user.
But exchanging links here and there — *especially* when done with clear editorial judgement (e.g., you're not just accepting dozens of link exchanges willy-nilly) — that's not the sort of thing Google looks down upon.
Hope that helps clear things up a bit!
Always nice to get some words from the horse's mouth.