> I tried to use the orgstruct minor mode, but it didn't seem to do
> anything, although I used exactly the same setup Bastien showed in his
> interview[1].
>
> After a while, I realized it was because I was using emacs in an
> xterm.  Steps to reproduce below.[2]

Some bindings, such as M-TAB, C-n or C-p, should work fine.

> Wrong setup, a bug or intentional?

This is a bug.  Can you please give this patch a try and see if it
corrects the issue?  Apply it on master (06cdb2d).  Thanks!