Ubuntu – Solarized Dark + Gnome Terminal + Vim + Vim-Airline

I installed the solarized dark theme for gnome terminal using https://github.com/Anthony25/gnome-terminal-colors-solarized and then with Vundle installed https://github.com/altercation/vim-colors-solarized. I added these lines to my .vimrc:

try
  " Solarized options
  let g:solarized_term = 1
  colorscheme solarized
catch                                                                         
endtry

set background=dark

I am also using https://github.com/bling/vim-airline installed using Vundle.

The problem is that in Normal mode vim-airline doesn't look great (text is very hard to read):

On my Mac with virtually the same setup it looks perfectly fine:

How do I get vim on my Gnome Terminal to look like it does on my Mac?