Try rxvt-unicode, it's a great, light terminal app for *nixes and can be compiled with 256 color support. (see the PKGBUILD: http://aur.archlinux.org/packages.php?ID=13060)

Most? I tried non-Linux OSs to see what you're talking about. PuTTY on Windows works perfectly. Yes, Terminal on MacOS X doesn't support 256 colors, but iTerm does.