I have already lost my colors when moving to Lion on my Terminal.app, the same happened when I moved to Mountain Lion, but oh surprise, the fix I found out for Lion didn’t work for Mountain Lion, because in Mountain Lion there is no xterm-color available as a choice of terminal type. The solution I found was to manually edit the configuration options of Terminal.app and so far it seems to work.
You will need (most probably) XCode installed in order to edit the config file which is a plist. You can find the config file in ~/Library/Preferences/com.apple.Terminal.plist. Since the ~/Library folder has been hidden since Lion, your best bet is to open up terminal and type:
open ~/Library/Preferences
which will open the Preferences folder in Finder and you can just find the config file and open it.
Before doing any edits you should quit Terminal, as it saves its settings on exit and it will override any changes you do.
To add the xterm-color option you’ll have to go to Root > Window Settings locate the name of your default theme (in my case that’s Pro) expand it and find the TerminalType key. Now just change the key to xterm-color, save the file and launch Terminal.