If you are advertising online there is always the big two - Google(Adwords) and Yahoo(Overture). I would also have a look at some online comics. The two bigest ones focusing on gaming are: * http://www.pvponline.com/ * http://www.penny-arcade.com/comic
There are about 50 other comics that focus on gaming. Each one focuses on different types of gamers. So if you can try different comics.
The most important thing is to make sure you know how well your campain is going. If you haven't set up a marketing funnel I would probably try to setup on of those first: * http://sethgodin.typepad.com/seths_blog/2006/01/understandin... * http://brianwong.com/blog/funnel-visualization-with-google-a...
If you have a revenue model you can even justify spending more money on advertising. Even if you are just trying to BUY market share it is worth know where you will get the most bang for your buck.
Nathaniel Brown - http://www.adinobro.com/