1. In addition to having a "Link To Us" page so that people can link to you, have a page of banners/links of people that are linked TO you.
Ex. I have an ot.com banner on my site, you could have a link to my site on ot.com. A simple swap.
This kind of thing might appeal to those people that have the 'What do I get out of it?' attitude.
2. Join some free banner exchanges. When I was running my website (Starkiller's Sci-Fi Battlefield), I was part of 3 or 4 different SW-related free banner exchanges.
Here, check some of these out:
The Jawa Trader Banner Exchange
The Star Trek and Star Wars Banner Exchange
The Star Wars Combine Banner Exchange
Then there are those "Top 100" sites:
Hit Rocket
Hapes Top 100