Hmmm, looks like the bug is caused by undo-tree, since when elpa-undo-tree 0.6.4-3 is installed tests are passed correctly. Moreover, when new upstream version of undo-tree is used (0.7.4, not currently in Debian) tests also are passed correctly.