I seem to recall Cutts saying that recip linking was ok in 'moderation'. also, if it happens, quite naturally if you ask me, between sites which are in the same geographical area or which have a similar or related niche, I can hardly see what google would find wrong with that. what the engines are concerned about is recip linking in vast amounts trying to 'game' the system.
exchanging links in your town or niche, for example, all of which can help enhance you visitors' experience (i mean who does have everything that anyone or everyone needs on their site anyway?) is good, especially if you are 'linking up' to a higher valued or more trusted site.
exchanging links with related sites is perfectly natural, in fact, that's how the whole darn internet works, people going from link to link/site to site etc etc. it's exchanging links excessively or with spammy websites that needs to be avoided.