New Avalon is located just east of Tyr's Hand in the Eastern Plaguelands. The town encompasses Scarlet Hold, the New Avalon Orchard, the Scarlet Tavern, the Chapel of the Crimson Flame, the New Avalon Town Hall, and the New Avalon Forge. The Scarlet Overlook and King's Harbor are located to the southeast, and Havenshire is to the north.
The town itself is instanced, and after Death Knights finish the quest line they are sent to the non-instanced Eastern Plaguelands where the ruins of New Avalon and Havenshire can be seen.
Avalon was a sacred island in Arthurian legend where the spirits of fallen heroes were said to go, including King Arthur himself.
New Avalon is therefore an appropriate name for the starter area of the death knights, who are themselves fallen heroes. Why the Scarlet Crusade would name a town in reference to the death knights is unknown.
It could however have another meaning, referring to fallen heroes who died in battle (or died at all for that matter) which would make more sense for the Scarlet crusade to name it "New Avalon".
The other approach is that the members of the Scarlet Crusade are fallen heroes themselves. They think highly of themselves (heroes) yet they failed to stop the Scourge from devouring their beloved homeland (fallen).
Most likely, it is an out-of-character detail for players to appreciate.