Variants with Colombia — Colón — Columbia — Columbus

Colom...

Colon...

Columbia...

Columbus...

On the first map of the city of Washington by federal city planner Pierre L'Enfant it was called the Permanent Seat of the Government. Newspapers encouraged an informal competition by printing suggested names sent in by readers. One anonymous writer suggested "Washingtonople", while others suggested "Columbus" and "Washingtonapolis".
As with most things in the new capital, a group of men got together to settle the matter. They met on Sept. 8, 1791, in George Town. There were a lot of items on the agenda, but eventually Secretary of State Thomas Jefferson, Rep. James Madison and three commissioners appointed by Washington to sell lots in the federal city got around to what it should be called. Some in the group supported naming it Washington. Others argued for naming it Columbia, after Christopher Columbus. Scott said there was great interest in Columbus because the 300th anniversary of his famous voyage was coming up the next year. A compromise was struck: the federal enclave would be known as the city of Washington, and the general area would be called the District of Columbia. There was no public proclamation of the new name, however. It appeared in print for the first time in a Sept. 17 George Town Weekly Ledger notice about the death of an assistant to federal city surveyor Andrew Ellicot. The man had been killed when a tree fell on him.

From: Linda Wheeler in the Washington Post on Feb 22, 2001. (longer excerpt of that article here).

Sources:

• The Probert Encyclopedia
• Heavens Above
• Joseph N. Kane, The American Counties. New York: Scarecrow Press, 1962.