Considering the game supports 640x480 resolution, I'm guessing the problem is with color depth. You should support both 16 and 32 bit color.
Of course, it may be starting up into 1024x768, in which case having 640x480 in the settings menu doesn't help any.
Of course, it may be starting up into 1024x768, in which case having 640x480 in the settings menu doesn't help any.