Terminal not displaying colors for directory listings

I don't know why my bash session doesn't show colors. I have tried Terminal as well as iTerm.

I have tried:

1. ls -G
2. Setting export CLICOLOR=1 and export LSCOLORS=GxFxCxDxBxegedabagaced
3. Using different themes such as solarized and something else

The versions of my software are:

1. bash: GNU bash, version 3.2.51(1)-release (x86_64-apple-darwin13)
2. osx: 10.9.2

I have Homebrew installed

I don't know what other information might be helpful. I spend a lot of time on the shell, this problem is becoming very annoying :)

edit: in terminal preferences, I have 'Declare terminal as: xterm-256color' and 'Display ANSI colors' along with 'Use bright colors for bold text'

I would suggest installing the GNU Core Utilities via Homebrew, which will give you the "Linux" version of ls (instead of the FreeBSD version that ships with OS X), as well as other powerful tools

brew update
brew install coreutils

You should then be able to show colors with:

gls --color

Additionally, read the caveats to configure your PATH so you can use commands like gls with their normal names, i.e. ls:

$ brew info coreutils
coreutils: stable 8.23 (bottled)
https://www.gnu.org/software/coreutils
Conflicts with: ganglia, idutils
/usr/local/Cellar/coreutils/8.23 (214 files, 10M)
  Poured from bottle
/usr/local/Cellar/coreutils/8.23_1 (214 files, 10M) *
  Poured from bottle
From: https://github.com/Homebrew/homebrew/blob/master/Library/Formula/coreutils.rb
==> Dependencies
Build: xz ✔
==> Caveats
All commands have been installed with the prefix 'g'.

If you really need to use these commands with their normal names, you
can add a "gnubin" directory to your PATH from your bashrc like:

    PATH="/usr/local/opt/coreutils/libexec/gnubin:$PATH"

Additionally, you can access their man pages with normal names if you add
the "gnuman" directory to your MANPATH from your bashrc as well:

    MANPATH="/usr/local/opt/coreutils/libexec/gnuman:$MANPATH"

In Temrinal's Terminal > Preferences select the profile for the session type you're using and check under the Advanced tab what terminal declaration you're using. Most likely the one selected doesn't support ANSI coloring. xterm-256color should support what you're expecting.