Looking at your post and your responses to others, it sounds like your problem is... screen. To test my hypothesis, try this ...
$ wget http://www.frexx.de/xterm-256-notes/data/256colors2.pl
$ chmod 755 256colors2.pl
$ ./256colors2.pl
... if you see 256 colors in the shell, but not in screen, the problem is screen. And, even if there are other problems, you are going to have to fix screen in order to have any hope of seeing 256 colors in emacs ;)
I recently fixed this situation for myself on a system where I don't have sudo by building a personal copy of screen. Screen is small and it is no big deal to do ... and, IMHO, emacs w/256 colors is well worth the bother.
On Linux 2.6.x I did this:
$ wget ftp://ftp.gnu.org/gnu/screen/screen-4.0.3.tar.gz
$ tar -xf screen-4.0.3.tar.gz
$ cd screen-4.0.3
$ ./configure --prefix=$HOME --enable-colors256
$ make
$ make install
Test the new screen out with ...
$ ~/bin/screen
$ ./256colors2.pl
... if it works, put this in your ~/.bashrc:
PATH=~/bin:$PATH ; export PATH
The screen I ended up with reports being an earlier version ...
$ ~/bin/screen -v
Screen version 4.01.00devel (GNUdf0777e) 2-May-06
... than the version on my system:
$ /usr/local/bin/screen -v
Screen version 4.00.03 (FAU) 23-Oct-06
But while they both claim to support 256 colors...
$ tput colors
256
Only the new build really does. Yeah!
M-x list-colors-display
lists more colors, but the ones after the first 8 are shown in the normal foreground and background colors (white and black), not the listed colors. – Cassiterite