For some strange reason at least Fedora ships screen and vim with 256 colors disabled. Here’s a quick guide how to enable 256 colors in vim and screen.
Add to you .vimrc file
set t_Co=256
Add following lines to your .screenrc file
attrcolor b ".I"
termcapinfo xterm 'Co#256:AB=\E[48;5;%dm:AF=\E[38;5;%dm'
defbce "on"
Also check that your terminal supports or has 256 colors enabled. At least gnome-terminals seems to have this by default. Enjoy combination of vim and screen with 256 colors. :)