I have the same problem. See an example here: http://www.grunder.no/grundere/20091006/svaksynte-ma-bli-grundere/
Click the link under the main text where it says "Del på Twitter" (Norwegian for "Share on Twitter"). When the new window opens, you can see the URL with ü, Ü and Ø in it, but then as it's redirected on Twitter, they are encoded (which is good, I suppose) – but they're not decoded back when inserted into the text field. I managed to get rid of the %20 for spaces by replacing them with plus signs, but as for the rest, I'm clueless.
