CalebCaleb is right in his comment. xterm is fairly old and you should consider switching to urxvt -- at least the 256 and utf-8 enabled version, refer to your package manager to install the right one.
I have an identical set up to yours -- awesome WM, vim, urxvt, tmux/screen -- and they all work well with 256 colours and utf-8. I have set TERM to xterm-256color in case you need to set this manually.
Hum... After your edit, can you check if the vim colour theme is properly defined for terminals?