I agree with many of the choices already made here, and Gregory's list on Page 1 would be more or less the same as my own. I think the case for releasing Jerzy Skolimowski's early work onto DVD is one of the most pressing - in addition to the previously mentioned 'Rysopis/Identification Marks None', 'Walkover' and 'Deep End', I'd suggest his extraordinary 'Barrier' - which boasts some of the most brilliant imagery anywhere in '60s cinema - and his Belgian-made 'Le Depart', which stars Jean-Pierre Leaud. These films seem to be unavailable anywhere, and if they were release I believe they would re-establish Skolimowski's status as one of the most significant figures of world cinema's 'second wave' (i.e. those who began making films in the wake of the original Nouvelle Vague, circa 1964-5).
Pavel Juracek is another figure long overdue for release in UK, given that he's also virtually unknown in this country. As someone else mentioned, the Czech(oslovak) New Wave is now associated too much with the social realism and comedy of Forman, Passer et al, while the avant-garde, Surrealist-affiliated side has been neglected. Juracek is one of the greatest exemplars of this second trend (albeit with elements of the first), though his filmography is not large. Might I suggest the idea of a 3-disc box set that included 'Every Young Man', his brilliant and experimental 'Case for the Rookie Hangman' and 'Josef Kilian/Postava k Podpirani'. As the latter film is only around 40 minutes, it could be supplemented on one disc by Martin Sulik's recent documentary/dramatisation about Juracek's life, 'The Key to Determining Dwarves' - which is also unavailable anywhere.
Jakubisko has also - rightly - been mentioned several times, but I'd also like to suggest another Slovak filmmaker from the same period, Stefan Uher - his first film, 'Sunshine in a Net', is often credited as one of the films that began the New Wave (although it is available on VHS from the Slovak Film Institute in a good print). Then there's his Surrealist 'The Miraculous Virgin' from 1966, which is now almost completely unknown but which sounds fantastic.
Has anyone mentioned the Romanian classic 'Iconostasis' by Christo Christov and Todor Dinov, which sounds like a Romanian equivalent of Andrei Rublev?
Chytilova's 'Daisies' and 'The Fruit of Paradise' are now available in not-bad prints from Facets, but her first feature 'Something Different/O necem jineho' isn't available anywhere.
Also, Second Run might not be the most obvious people to release these, but I can't help mentioning Jacques Rivette's masterpieces 'L'Amour Fou' and 'Out 1' (how about a box set with both the 12 hour and 4 and a half hour versions??), which have never been released, at least in subtitled form, anywhere on VHS/DVD.
And I'd like to second the suggestion for a release of Jan Lenica's solo animations, especially his reputed masterpiece 'Labyrinth'.