New Matroska elements CueRelativePosition and CueDuration cause unseekability
mkvmerge's latest release v5.9.0 writes the two elements mentioned in the summary by default. While CueDuration is only written then a block's duration does not equal its default duration (e.g. with subtitles), CueRelativePosition is always written.
Unfortunately VLC does not skip unknown elements by default, though you can turn it on in the preferences ("Dummy elements"). This causes VLC to abort reading the file at the very start of the cues resulting in not being able to seek (properly) in such a file.
Turning on "Dummy elements" fixes this immediately; now seeking works as it has before.
Rationale for adding those two elements was actually to improve seeking in files by providing players exact locations where to seek to. The rationale is explained in two threads on the Matroska devel mailing list: for CueDuration and CueRelativePosition. Note that the EBML ID for CueDuration mentioned in the linked email is wrong. However, the official specs page contains the correct information (0xb2).
Note further that the latest official release of libmatroska does not yet contain support for that element. Therefore mkvtoolnix includes a copy of the current version available via Subversion.
I've verified both the presence of the issue and the workaround on Arch Linux with VLC 2.0.4 and on Windows with 2.0.4.