Terminal input does not wrap correctly, or at all

For a while now, I've had this persistent issue on all my terminals, from the gnome default and tilda which I both use to ones I just gave a quick whirl, where my input will overwrite the start of its own line when it should wrap, and only wrapping on the next line.

Pressing Ctrl-A to return to the start of the line will instead return me somewhere up in the line before my first input line, from which any more input just gets very weird.

Because this is a really bad explanation and hard to visualize, here's how it looks:

Does anyone know what this is? It doesn't only happen under certain circumstances, it's a permanent thing that is always there from start to finish of every session in every terminal emulator.

Output of printf "%s\n" "$PS1" "$COLUMNS":

leod:~$ printf "%s\n" "$PS1" "$COLUMNS"
\[\e]0;\u@\h: \w\a\]${debian_chroot:+($debian_chroot)}\[\033[01;32m\]\u\[\033[00m\]:\[\033[01;34m\]\w\[\033[00m\]\$ 
80

Output of stty -a:

leod:~$ stty -a
speed 38400 baud; rows 11; columns 140; line = 0;
intr = ^C; quit = ^\; erase = ^?; kill = ^U; eof = ^D; eol = <undef>; eol2 = <undef>; swtch = <undef>; start = ^Q; stop = ^S; susp = ^Z;
rprnt = ^R; werase = ^W; lnext = ^V; discard = ^O; min = 1; time = 0;
-parenb -parodd -cmspar cs8 -hupcl -cstopb cread -clocal -crtscts
-ignbrk -brkint -ignpar -parmrk -inpck -istrip -inlcr -igncr icrnl ixon -ixoff -iuclc -ixany -imaxbel -iutf8
opost -olcuc -ocrnl onlcr -onocr -onlret -ofill -ofdel nl0 cr0 tab0 bs0 vt0 ff0
isig icanon iexten echo echoe echok -echonl -noflsh -xcase -tostop -echoprt echoctl echoke -flusho -extproc

It's possible your terminal is not recognizing the window size correctly. I found a related question in U&L Stackexchange, and someone suggested the below way of checking whether this is what's going on:

Type

shopt | grep checkwinsize

If the output is not:

checkwinsize    on

You can use

shopt -s checkwinsize

to activate. To deactivate: shopt -u checkwinsize