gnome-terminal does not allow changing the title

I've selected "Replace initial title" setting in gnome-terminal's preferences, but it just shows the default title "Terminal". After reading this answer, I added this to my .bashrc:

PROMPT_COMMAND='echo -ne "\033]0;${USER}@${HOSTNAME}: ${PWD/$HOME/~}\007"'

and also commented out this line:

#PS1="\[\e]0;${debian_chroot:+($debian_chroot)}\u@\h: \w\a\]$PS1"

After restarting terminal, it started to show user@hostname: ~/currentdir in its title, changing it whenever I cd to another directory. But it still does not change when I launch CLI programs like cmus and vim (vim, for example, sets current filename as a title).

I've installed rxvt and everything works fine there.

Ubuntu 13.04, gnome-terminal 3.6.1.

My .bashrc - almost the same as shipped with default ubuntu installation.

First, you have something contradictory in your question. You said, "it started to show user@hostname: ~/currentdir in its title, changing it whenever I cd to another directory", but the image attached said something else. I am almost sure that if you've selected "Replace initial title" setting in gnome-terminal's preferences and if you use this ~/.bashrc file as you said, your terminal should look like in the following image:

Second, you're totally wrong with: "vim, for example, sets current filename as a title". To do this, you must to heve a file named .vimrc in your home directory with the following code inside:

let &titlestring = $USER . "@" . hostname() . ": vim " . expand("%:t")
if &term == "screen"
  set t_ts=^[k
  set t_fs=^[\
endif
if &term == "screen" || &term == "xterm"
  set title
endif

And one more thing: I don't understand yet exactly for what do you using that if from the 11th line until 40th line in your .bashrc file, but setting up TERM="gnome-256color" at the line 33 may be a problem in this case. So, I suggest you to comment that line, or to remove all the code between lines 11 and 40.

After all of this done, when you will use vim, your terminal should look like: