I'm used to tmux, so I want Byobu to use Ctrl+B as the escape sequence. I hit F9, Change escape sequence, and B.

But when I hit Ctrl+B on the shell, it moves one character back instead of letting byobu/tmux handle it.

First, I typically don't use the F9 menu stuff, so this is relatively new to me. However, when I did that and pressed B (no ctrl since that is assumed/forced), it immediately worked correctly (without a restart). I'm not certain why it would not work with your configuration.

Since byobu is really keeping its own store of configuration items and forcing screen/tmux to use its versions, you can find what to change by looking in ~/.byobu/, and how to change it by reading the respective man/help pages.

You can edit byobu's config files behind the scenes (not always a good idea, but should be acceptable here). Since byobu uses either screen or tmux (based on what is installed), the answer can reside in either ~/.byobu/keybindings (for screen) or ~/.byobu/keybindings.tmux.

I played around with using both screen and tmux ... choose one (defaults to tmux if installed, I think) and go with it.

First things first

Check to make sure that echo $HOME prints what you expect (not a blank line). If there is not a directory called .byobu within that home directory, then either the byobu installation is dorked or you don't have the correct permissions set in your home directory; try mkdir "${HOME}/.byobu", and if it doesn't work than that could be part of your problem.

screen

From man screen

...

 escape xy

 Set  the  command  character  to  x and the character generating a literal command
 character (by triggering the "meta" command) to y  (similar  to  the  -e  option).
 Each  argument  is either a single character, a two-character sequence of the form
 "^x" (meaning "C-x"), a backslash followed by  an  octal  number  (specifying  the
 ASCII  code of the character), or a backslash followed by a second character, such
 as "\^" or "\\".  The default is "^Aa".

...

The first line of ~/.byobu/keybindings should have byobu's source command, so don't change it. After it, add the following:

escape "^Bb"
register x "^B"
bindkey "^B"

(This is taken verbatim from what byobu did to my install. Historically -- since I use screen/tmux without byobu much of the time -- I actually just set:

escape "^Bb"
defescape "^Bb"

This may not be the best way, and it has some historical kludgeness to it, but it works for me.)

tmux

Similarly, from man tmux:

       prefix key
               Set the key accepted as a prefix key.

       prefix2 key
               Set a secondary key accepted as a prefix key.

My ~/.byobu/keybindings.tmux doesn't have a source command, so my file only contained the following:

unbind-key -n C-b
set -g prefix ^B
set -g prefix2 ^B
bind b send-prefix

If This Doesn't Work

Knowing your OS and software versions will be useful. I tested this on ubuntu-13.10 with byobu-5.60-0ubuntu1, screen-4.0.3-14ubuntu10, and tmux-1.8-4.