Legend has it that if you change your screen depth in xorg.conf to 8-bit, then 256 colour titles magically start working under Wine. Not sure if it's true, but I'll try it out soon enough with some stubborn Sierra titles.
Of course, the other way to get around this is to just grab a PSX ISO of Lomax, and a recent PlayStation emulator (don't forget the BIOS image!), then play it like that.