I'd hazard a guess it isn't an East Coast/Midwest thing, or isn't exclusively, anyway. It may be more complicated than that.
My dad, who was raised in a more or less rural/small town situation, tends to say "cellar." I was raised in a more urban atmosphere--relatively speaking, anyway--and I tend to say "basement." I also seem to make a distinction: a "basement" is "finished" (some type of flooring, maybe a drop ceiling with inset lights), whereas a "cellar" is "unfinished" (dirt floor, no walls except the foundation, maybe light bulbs on wire for illumination). But after I've spent some time with my dad I tend to fall back into some of his speech patterns and say "cellar."
That makes sense, up to a point. I grew up in a suburb, so urban-ish, and I say basement. But what about Chuck? Chuck, didn't you grow up in an urban area? Or maybe when you came up with your username you couldn't think of an appropriate rhyme for "basement"?
I think a basement can easily be unfinished. In real-estate ads, where they call it "basement," at least around here, they specify whether it's finished or unfinished. My basement is more on the unfinished side, though it currently has old linoleum over part of the floor and a drop ceiling. But you're right, some of the basements I have seen -- carpeting, nice furniture, big-screen TV, maybe a bar and/or pool table -- I can't imagine calling those cellars. You can barely even call them basements!
And those places that have narrow wood-plank steps down into a cave-like concrete room, where the walls are lined with shelves of home-canned food vegetables and jellies that the mom "put up" herself with produce from the garden and they can be kind of scary? Definitely cellars.
Chuck, what was your former dwelling space like?