A while back I was setting up some sites for a Finnish customer using Amazon Route 53 as the DNS provider. It wasn't quite as easy as I would have imagined.
The hosted zone could not be saved because: Domain Name contains invalid characters or is in an invalid format.
It turns out Route 53 does not handle Scandinavian Letters (like ä and ö for example) automatically, rather it gives you the unhelpful error seen above. It took some googling to get to the bottom of the problem.
To make things work you have to encode Scandinavian letters to ASCII using Punycode. Once you know that, there are tools available that make the encoding easy (for example here and here).
The Punycode encoding itself is quite fascinating and you can read about it in Wikipedia. Here's an example of Punycode in action:
hyvää.fi encodes to xn--hyv-slaa.fi