A properly designed and constructed chimney does not need a fan; it operates by natural draft. Before doing anything, you should have the chimney inspected for safety and have a draft test performed. Basements are not ideal locations for wood stoves or fireplaces as they often have draft difficulties.

As for your choices, a fireplace is extremely inefficient as a heating source. Nearly all the heat goes straight up and out through the chimney. Modern EPA certified woodstoves or inserts are much more efficient but may experience more drafting difficulties than the old stove in a basement.

You can find a world of information at www.hearth.com. Your local fire department should be able to give you the name of a certified chimney sweep for inspection and advice.

Thanks for the information! I know what it's like to have a regular fireplace, and I have to admit that I wasn't crazy about going without a wood stove because the last house I lived in had a fireplace and it had a ventilation system where you'd just flip the switch and the fan would come on. It did a great job with pulling all the smoke and soot up, but the heat went with it as well.
I've got someone coming to inspect the chimney and clean it out, and I've already found a replacement stove that I'm hoping to have put in within the next few weeks. This particular situation just threw me for a loop because I've never had a fireplace or wood stove in a basement before. If everything works as planned, I'll keep my fingers crossed for lower electric bills this winter!