Hello, I'm working on a complex game with a really in-depth story and cool combat/crafting. I've made some good progress but I was wondering if anyone knew where to advertise the game to get publicity? I know text-games have a sort of cult following but I think that my story-telling will be able to attract people. Any ideas?

You're making the game with Quest?

It kind of depends on how much game is in your game so to speak, but some good places might be Reddit (you'll need to find the appropriate subreddit...there's one for text adventures but also many more that might be suitable I'd guess), Bay12 (home of Dwarf Fortress, whose forum members play a lot of other similar retro/complex games), SomethingAwful (kind of some crossover with Bay12). Of course there's the Intfiction forum too. Perhaps TIGSource if your game was pretty (or cool) enough.

Are you a regular member of any sizable forum? In my experience the best way to advertise a game is in a place with a decent amount of activity where you've already built up some rep with the community. If you can't do that the next best is for a member of such a community to find your game on a more obscure site, but your game would need to be a little more polished to spark someone's interest I think.