It seems that byobu‘s defaults don’t play nice with emacs, eating important key sequences such as <C-h> and breaking color schemes. Adding the following line to ~/.byobu/.tmux.conf fixed the issue:

set -g default-terminal "screen-256color"

(from https://bugs.launchpad.net/byobu/+bug/1544983)