OK, I feel really stupid now.  I've spent last hour figuring out how
emacs figures out how to use colours.  I used different terminals,
played with TERM and COLORFGBG and Xdefaults.  I even created a new
user just to test with clean environment.  And, it comes to be that
years ago (possibly trying to mitigate different problem) I've set
alias emacs="emacs -r" in my bashrc and it just started working with
23.4.  I apologize for wasting your time and thanks for all the help.