Since the game runs except in a specific mode (full-screen) I can comfortably say that this is a video driver issue.
We (Basilisk Games) didn't write the OpenGL interface code for Eschalon (it is part of the compiler) so there is very little we can do to change the way Eschalon talks to specific video drivers. I would suggest trying different video drivers if there are any available for your chipset. I would also check some Linux-specific forums for help, look through these
Linux support forums thoroughly, and also check the forums on www.playgreenhouse.com
as I know there is discussions over there on getting 64-bit Linux to run Eschalon.
I am sorry I don't have a better answer for you at this time. As a final suggestion, you could try running the Windows version via WINE and see if you get better performance.
We'll certainly let everyone know if anything changes on this side (i.e. improved OpenGL support for certain chipsets).