All the important terminal emulators: xterm, rxvt, gnome-terminal, konsole support 256 color terminals. Things like emacs22 or vim7 work much better on 256 color terminals.
On the other hand, many applications do not work with 256 colors (also ncurses won't do this unless you bump to the ABI 6 changes). It's probably a good thing (except for efficiency) to deliver 256color-capable terminals, but not a good idea to force everyone to change to use it.