Most of the walls in the old part of my house are plaster. Hard, nasty, amazingly solid plaster. While this is nice in some areas, there's others that it's rather annoying -- such as on the stairs (previous owners have screwed in a banister ... with regular screws, awesome)
I would have no problem popping out the plaster and exposing some brick, or even better, find some wooden slats, get some insulation in there and maybe toss up some drywall. Yea, I know, it'll be a mess, but oh well, I got a shop vac :-)
Anyway, what's behind those walls? (and someone needs to make a -plaster- tag !)