I use Solarized for all my editors but had the hardest time trying to figure out why vim in terminal mode had no syntax highlighting.

Fortunately the fix is incredibly easy [thanks to my co-worker] and probably well known to many OS X vim users relying on Terminal.app: In your Terminal preferences (⌘,) under Settings > Advanced tab set Declare terminal as: to "xterm-256color". Restart your terminal sessions and 256 color themes will now work.

I figured out what the problem was from the excellent Xoria256 color theme which helpfully reports when your terminal is not running in 256 color mode with a message during vim startup...

if &t_Co != 256 && ! has("gui_running")  
  echomsg ""
  echomsg "err: please use GUI or a 256-color terminal (so that t_Co=256 could be set)"
  echomsg ""
  finish
endif

As this is for OS X Lion's Terminal.app you won't need SIMBL or any other hacks to get this working.