Mac OS X's Terminal.app does not support 256 colors. Submit a feature request to Apple if you would wish it did -- I do. Apple Bug Reporter: http://developer.apple.com/BugReporter/
I use iTerm mostly because a) tabs! b) I'm a sysadmin and have a ton of bookmarks for ssh connections to various servers (frequent ones with keystroke shortcuts). c) profiles are handy.
iTerm seems to support 256 colors.
Edit: Terminal.app seems to support tabs, must be new in Leopard :)
I started using 256 color terminal a couple of years ago...there are a handful of really nice vim color schemes that take advantage of it. I'm a sucker for nice syntax highlighting, and this change made me happy for days. I found myself wanting to write more code so I could see it in the all it's colorful glory. That feeling has passed, however, so maybe I need to find another color scheme to try.
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.
Yeah, this was an unpleasant surprise for me when I started using a Macbook for some coding. My 256 color vim color scheme (desert256, highly recommended!) would just blink repeatedly until I typed in t_Co=8 ... never thought moving from a Linux machine to a Mac would mean decreasing your colors!