When the emacs-X11 package is removed, a trigger in the emacs-nox package is supposed to put the symbolic link from /usr/bin/emacs to /usr/bin/emacs-nox back in place. However, this trigger runs *before* emacs-X11 is removed, so the symlink is replaced, and then /usr/bin/emacs is removed, cancelling what the trigger just did. The solution is to make the trigger run *after* removing emacs-X11, by replacing "%triggerun" with "%triggerpostun".
Fixed in the devel tree.