Ive never liked the name Magic. A pretty wierd name for a sports team. Orlando use it because of the city's connection to Disney world, but for Melbourne, its a strange name. Going with something new (not Magic and reinstalling an old franchise) is the right move.
Phoenix is an interesting choice, rise from the ashes (even though its a brand new club) makes it a bit confusing, though it has a greek connection, maybe tying in with Melbournes greek community - in a similar way to the Celtics connection to Boston's Irish community? Don't really know, just looking for a reason... i dont mind it.