It seems to me you have to focus on your demographic and spend some time figuring out their top websites, then figure out ways to partner with them. It sounds obvious but if you spend the money on getting Digg frontpaged or an ad on Penny-Arcade the customers presumably won't actually stick, since they're not your target audience.

Can you set up a myspace page? Add Facebook integration, a Facebook fan page, etc? Advertise on Livejournal? Celebrities is a good one as someone else mentioned, also fashion and style sites - with the death of print, could you even afford to advertise in Cosmo or the teenage equivalents? As well as casual gaming sites and possibly MMO sites, as plenty of women play MMOs and look for other distractions as well.

To be honest although I'm a twentysomething girl I'm somewhat atypical and don't really know what sites my 'demographic' visit - but you need to find that out. Maybe look at some of your competitors too, there are a ton of casual games out there.

If you've got 10k users already maybe you can incentivise them to recruit a friend with some of the marketing budget as well. Free months/extras etc.