Since I had to dig a little to find how to make vim works fine in 256 color mode (using set t_Co=256), I'm pasting it here so it might help some people :)

So, I only had to add this:

termcapinfo xterm 'Co#256:AB=\E[48;5;%dm:AF=\E[38;5;%dm'
defbce on

to my .screenrc file.

Then just screen -r again and it should work fine (did for me, on a Debian Lenny, and an Ubuntu 10.10)

edit: seems that in some cases, you have to start a new screen session :-/