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.