Terminal prompt overwrites current line

You've completely banjanxed the Bourne Again shell's idea of what's been printed and what it has to erase/rewrite as it displays command history and lets you edit the command line.

Breaking your prompt down into sections:

1. \[\e]0;\u@\h: \w\a\] — non-printing characters, properly enclosed
2. ${debian_chroot:+($debian_chroot) } — printing characters only, presumably
3. \[\033[01;36m\] — non-printing characters, properly enclosed
4. \u@\h — printing characters only
5. \[\033[00m\] — non-printing characters, properly enclosed
6. \033[01;34m\] — non-printing characters, improperly enclosed so the Bourne Again shell does not know that they are
7. \w\033[00m\] — an erroneous mixture of printing and non-printing characters
8. [$(type __git_ps1 >/dev/null 2>&1 && __git_ps1 "(%s)")] — printing characters only, presumably

I've given this advice before, but it is general advice that applies here as well:

• Use either \e or \033 consistently, for your own sanity.
• Make your \[ and \] strictly matching non-nesting pairs.
• Make sure that all non-printing sequences are within \[ and \] (and that, conversely, that all printing sequences are not).

(This is why I personally prefer the Z Shell and its alternative prompt expansion mechanism for when I want wacky coloured prompts. It knows that things like %F{green} aren't printing sequences, without having to be told; and it also works out the correct escape sequences from terminfo, without having them hardwired.)