Is it an American passport? If it comes from a country which uses ö as part of its alphabet I don't see what would be surprising.
I keep on meaning to look into synchronizing my birth name (with an ł and a ó, latter is in 8859-1 but not the former) with my legal name in Canada, but I consistently conclude I can't be bothered...
I don't know about the US, but I made a series of Freedom of Information requests in the UK to find the answer to exactly this issue there, and was somewhat surprised to find that (in Northern Ireland at least) supposedly any Unicode character is valid: http://nothing.tmtm.com/2008/11/irene-and-irene-and-%D0%B0%D...
Whether that extends to the snowman character and the like is still an open question...
Very interesting about the situation in NI. Thanks for the link.
And anyway, nothing is stopping you from photoshopping your drivers' license to say whatever name you want. When Facebook asks you to verify your "real name", just give them a photoshop. Or don't use Facebook.
Incidentally, I have a friend whose passport says "Ingy döt Net". Yup, an O with umlauts. And that's his legal name.
So I don't really see an issue here.