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 :)