I fiddled with all of the options available at that setup screen and none made a difference.

I should probably have explained it better, the game is fullscreen in the sense that it fills the entire screen, but the only colour is in a 800x600 box in the middle, the rest of the screen is just black?

It's difficult to describe.. it's like it's running in a 800x600 window, but the rest of the screen is blacked out.

Thanks for the help =]