Binary package hint: openoffice.org
To reproduce:
1) Create a valid video file: "foo.ogv".
2) Verify that it plays in a media player.
3) Make a copy of the file called "åäö.ogv"
4) Create a directory named "åäö" and make another copy of the video file "foo.ogv" in there
5) Create a new presentation in OpenOffice Impress
6) Insert each video file into the presentation using "Insert->Movie and sound".
7) View the presentation
Expected result:
Each video file is represented by a video object in the presentation when editing. They all play in presentation mode.
Actual result:
Only the video "foo.ogv" works as expected. The files "åäö.ogv" and "åäö/foo.ogv" are represented by an audio icon instead of a video object when editing the presentation. They do no play when viewing the presentation.
Using a fully updated Karmic as of now.
Is that limited to movies in impress in your case because on my machine OOo can't open any files / documents with non-english names.
ver. 3.2 on lucid here.