I used to use Personal Paint for this sort of thing when I was making my AB3D2 mod. I would make various wall textures (also "borrow" from doom, quake etc.) and try to get them down to 32 colours or so each. Then load them as brushes onto a 256 colour image with the floyd-steinberg remapping enabled, before adding them. I seem to recall the results weren't at all bad.
