Don't know yet if the code change belongs in Undo Tree or Emacs but
the recipe is:

  • Start Emacs in scratch buffer with global-undo-tree-mode enabled
  • Go to BOB and insert "xxx"
  • Select first line
  • undo-tree-undo in region
  • undo-tree-redo in region
  • undo-tree-visualize
  • Navigate down (redo)*
  • Navigate up (undo)

Upon the navigate up, this error occurs:

  Debugger entered--Lisp error: (error "Unrecognized entry in undo list
undo-tree-canary")
     signal(error ("Unrecognized entry in undo list undo-tree-canary"))
     error("Unrecognized entry in undo list %S" undo-tree-canary)
     primitive-undo(1 (undo-tree-canary))
     undo-tree-undo-1(1)
     undo-tree-visualize-undo(1)
     call-interactively(undo-tree-visualize-undo nil nil)
     command-execute(undo-tree-visualize-undo)

* Sometimes the navigate down hangs with backtrace:

  Debugger entered--Lisp error: (quit)
     undo-tree-copy-list((nil))
     undo-tree-redo-1(1)
     undo-tree-visualize-redo(1)
     call-interactively(undo-tree-visualize-redo nil nil)
     command-execute(undo-tree-visualize-redo)

Don't know if it's related or not.

This recipe does not cause a problem with Emacs 24.3.

The following commit is suspicious:

commit 0c180ea96c022923ef18a255d0492bdb5ad04e02
Author: Aaron S. Hawley <aaron.s.hawley@gmail.com>
Date:   Tue Jan 8 14:13:31 2013 -0500

    * lisp/simple.el (primitive-undo): Move from undo.c.
    * src/undo.c (Fprimitive_undo): Move to simple.el.
    (syms_of_undo): Remove declaration for Sprimitive_undo.
    * test/automated/undo-tests.el: New file.

The commit moved primitive-undo from C to Elisp. In the process, it
added an else condition not present in the C code:

+             (t (error "Unrecognized entry in undo list %S" next)))))

The consequence of this bug is that when using Undo Tree, recent undo
history can become completely inaccessible.

I should note that if I don't undo in region, Undo Tree has never run
into any problems with the Emacs on trunk.