The issue occurs because the rxvt-unicode (urxvt) terminal supports only 88 colours whereas tmux terminal supports 256.
Output from urxvt:
susam@nifty:~$ tput colors
88
As a result, when tmux starts, it uses only 8 colours
susam@nifty:~$ tput colors
8
Adding the following tmux command to ~/.tmux.conf doesn't help.
set -g default-terminal screen-256color
With that line in ~/.tmux.conf, when tmux starts, it seems to be using 256 colours.
susam@nifty:~$ tput colors
256
However, it doesn't help because although tmux seems to be using 256 colours, the underlying rxvt-unicode (urxvt) terminal cannot display them properly since it supports only 88 colours. As a result, Vim still displays colours that are too bright.
Solution: Install rxvt-unicode-256color package.
There is an rxvt-unicode-256color package available in Debian that comes with urxvt terminal that supports 256 colours. Installing rxvt-unicode-256color fixed the issue.
The commands I used:
aptitude update
aptitude purge rxvt-unicode
aptitude install rxvt-unicode-256color
The colours appear a little bit different now.
But the experience is consistent with tmux.