If full screen isn't working, you might be able to run the game windowed.
There are instructions at http://www.wadjeteyegames.com/faqs/
In your game’s folder, there is a file called “winsetup.exe”. Run that program, and you will gain access to the game’s setup options which include windowed mode.
There may also be a "Force Alternate Letterbox Resolution" option available when you run the winsetup file.