I am having an issue when I open Vim, but only if I am in a tmux session.
It normally looks like this:

but inside tmux looks like this:

My patched fonts are working, so I am unsure why this is occurring.
My tmux config looks like:
source "/Users/damien/anaconda/lib/python2.7/site-packages/powerline/bindings/tmux/powerline.conf"
set-option -g status on
set-option -g status-interval 2
set-option -g status-utf8 on
set-option -g status-justify "centre"
Tmux needs to know that terminal supports 256 colors, or it will not work. Note that it is not only powerline that is missing colors: &number column is also missing them, so does ~ characters, thus going to powerline bug tracker with this problem is invalid.
If tmux knows that terminal supports 256 colors check that Vim knows that tmux supports them. I do not see that you have set default-terminal option to screen-256color, otherwise it usually thinks that only 16 colors are allowed.
Thanks. Adding set -g default-terminal "screen-256color" to my .tmux.conf resolved the issue.
I encounter a similar problem. I add this to the ~/.bashrc:
export TERM=xterm-256color
Most helpful comment
I encounter a similar problem. I add this to the ~/.bashrc:
export TERM=xterm-256color