The Terminal application defaults have a problem passing colors with Ubuntu and other types of Linux machines with properly formed .bashrc files. This is because those systems do not know how to interpret the Lion xterm-color256 terminal declaration.
The fix is to change this setting to xterm-color. This needs to be done for each Terminal default. Click on each (Basic, Grass, Homebrew, etc) and then click on the Advanced tab. From there, just set the Declare terminal as: to xterm-color and close.
This can also be done through the command line. These settings are stored in the com.apple.Terminal.plist per user, in their ~/Library/Preferences. The key for each is in TerminalType, which should read:
TerminalType = "xterm-color";
This small issue pales in comparison (especially because it is easily remedied) to how great the ability to take Terminal into full screen mode, have it state fully open and show the last run commands, assign background images and other little cool tricks are. There are also lots of new commands in Lion, such as tmutil that you’re sure to love if you haven’t made the upgrade yet!
