The game's colors are messed up, it's like I'm seeing the opposite color of what I should?
I had the same problem with Fallout, but thanks to GOG I found out that by fiddling with the .ini file graphics setting I could get it to work, but...
The game has an .ini file AND a graphics section... but I don't know what to do!

Could you copy and paste the contents of the ini file so I can take a look at it? Also what OS and video card are you using?
Have you tried the different compatibility settings as well?

; Postal Plus
; NOTE: Be careful when modifying this file!
[Video]
Type =DIRECTX
GammaVal = 147
UseCurrentDeviceDimensions=0
[Audio]
Type = WINMM
DeviceBufTime = 300
DeviceRate =22050
DeviceBits =16
[Paths]
CD =C:\Program Files\GOG.com\Postal Classic and Uncut\
HD =C:\Program Files\GOG.com\Postal Classic and Uncut\
VD =C:\Program Files\GOG.com\Postal Classic and Uncut\
Sound =C:\Program Files\GOG.com\Postal Classic and Uncut\
Game =C:\Program Files\GOG.com\Postal Classic and Uncut\
Hoods =C:\Program Files\GOG.com\Postal Classic and Uncut\
[Game]
UseCrossHair = 0
RecentDifficulty = 5
[Input]
UseMouse = 1
[Keys]
[Mouse]
[Joystick]
[Multiplayer]
HostName = Postal Host Name
Name = Dude
Server = 10.11.12.13
[Realms]
File = res/levels/Postal Plus realms.ini
[Features]
[Volumes]
[Demo]
InitialTimeOut = 60000
PersistentTimeOut = 60000
NumAvailable = 3
[Title]
Duration1 = 4000
Duration2 = 4000
Duration3 = 4000
Duration4 = 4000
[Can]
TakeSnapShots = 0
[Debug]
DisplayInfo = 0
I'm using Vista and I have a ATI Radeon HD 2400 Pro
I also just noticed that Windows wont let me edit the files... I must admit I don't know how to change the proper attributes in Vista...

Hmm can't see anything in the ini worth changing.
If you rightclick the postal shortcut and go to properties, then the compatibility tab and tick the check box for compatibility mode then use the dropdown box and try windows 98 compatibility mode. You could also try disabling visual themes.
If that doesn't work if you find postal in your start menu is there a settings launcher or a settings menu in game that might have different render options so say change it from direct3d to opengl etc?

That didn't work... But doesn't that graphic option say "DIRECTX"? If I knew how to get Vista to let me edit that file I could try switching that to OPENGL or Direct Draw?

Apparently I had open Notepad as an admin?
I switched DIRECTX with DIRECT3D and the issue seems to be solved!
I do see the graphics issue for half a second every now and then, but it's pretty much solved in my book! HUZZAH!
Thanks! :3

While this thread is marked as 'Solved by Tanukitsune' there is no posted solution. I am having this issue as well. Setting for Compatibility or 256 colour mode is not yielding to progress. No compatibility setting is correcting this issue.

Running Windows 7 Ultimate64bit
AMD Radeon 7700 Series (13.152.1.8000)

Edit: For whatever reason the entire thread does not display if you access the thread from the Community hub. When I found the same thread in teh Support section, it was complete. This is odd. Anyways, I'll give this fix a shot.

Edit2: Not only did switching to Direct3d not work, I had a hard lock up on my PC.

I also have this issue with AMD/ATI Graphics Drivers 13.9 on AMD Radeon 6900 series, and I did not had this issue with older 13.1 drivers. Many older games now have problems with newer catalyst drivers. Maybe you could try installing older drivers to check whether it would work for you.