The bug is probably in your bash startup files (incl: ~/.bash_profile (or ~/.profile), ~/.bashrc, /etc/profile, /etc/bash/bashrc, or anything sourced by one of those). Basically, it's doing something similar to this:
PROMPT_COMMAND='echo -ne "\033]0;${USER}@${HOSTNAME%%.*}:${PWD/$HOME/~}\007"'
But it needs to be:
PROMPT_COMMAND='echo -ne "\033]0;${USER}@${HOSTNAME%%.*}:${PWD/#$HOME/~}\007"
(The leading # makes it work like ^ in regex: anchors at the beginning.)
I have seen bashrc that have a variant specifically for screen (eg to use screen's title commands instead of xterm), so you may have to change this more than once. (Why they couldn't just parse termcap/terminfo? I dunno.)
Note that PS1 isn't affected by this as can be seen in your screenshot.
(Edit: and yes, this would be WTF worthy if it's the distro's bashrcs that are doing this. In fact, I just checked and my Gentoo system bashrc has this bug so others may too. You'd think distro maintainers would actually READ bash's manpage. And if turns out the bashrc came from upstream (==bash), that would double the WTF-ness :) .