Those who have seen them say they look like knee-high bearded men . They build walls of dirty grey brick that appear to be made of cinders and ground bones. Any tool used to break through these bricks will become useless or dulled (consumes tools and spikes / -1 to weapons until worked on by a smith). Wallers work quietly and and quickly; blocking a 10' corridor in a as many minutes. They will flee if provoked but will return again and again until the spot they were walling is walled.
This is my take on a fairy tale-like monster. I was spurred on by this post. I'll try to come up with some more. The idea here is not that players will be tricked into losing their way ( the bricks look different than surrounding dungeon) or even that it will consume resources (eating up spikes to break through) just that it is odd and makes little sense. It will hopefully give players the heeby jeebies and have them wondering what else might lurk in the underworld.