I was reading this article on the fact that the names for the north and south islands of New Zealand were never legally registered, and I like this suggestion from one commenter.

Why not pick names from Middle Earth to get the tourist numbers back up?

Gondor and Mordor? Wellington should be changed to Hobbiton, Auckland Rivendell. The English names are ugly anyway.
Stephen McPhillips, Denmark, from New Zealand