This is caused by a bug in the video mode enumeration code.
The bug may be overcome by using the "voodoo 3" patch (this is actually a small text file which overrides the default search of modes and specifies exactly what texture memory etc will be available).
Verified as fixing:
TNT, TNT2, Voodoo3, G400, GeForce (all), Radeon (all).
In fact it should fix all graphics cards with 32Mb or over.
This patch is available from here.