You can hav a links page just keep it well organized and highly relavant. The proof is in the search results - millions of websites rank well who also have links or partner pages. The important thing to remember is to publish links and get links (through exchange if possible) with high quality, relevant sites in a normal volume. Avoid low quality high volume methods.
For link exchanges, you have to be proactive, I believe. You can't just say, "Link to us and we will link to you," and expect people to find you.
I haven't done link exchanges for a while, but i am looking into doing it in a very precise way in the near future. I will most likely NOT have a "links" page that links out to other sites. Instead, I will find a page on my site that gets good traffic, and then link out to the home page of a partner site. (I will clearly state to visitors that this is a related site). Then I will ask them to do the same.
If they don't have a reciprocal link up within ten days, then I will move on to a different site.
It's easier to just find the the most juicy, old and niche related link/resource pages and pay to get on there. Don't target any anchor text, get them to provide good content with your link and it works great.