This attitude makes me want to vomit. The American Exceptionalism attitude of "we're the best country on Earth" is the root of so many problems in today's world.
Please check your ego.
A) Please do some research and determine if in fact you must cede your US citizenship in order to become a Columbian citizen, plenty of countries have dual-citizenship agreements with the United States.
B) "gave up one of the most valuable things anyone could have" -- Please qualify that. What exactly does he get for his American citizenship? Sure he can live here without being hassled for a Visa, but if he's married to an American citizen, then that point is moot. This isn't Sweden where citizenship entitles one to heavily subsidized healthcare/childcare/higher education or Switzerland where citizens might soon be entitled to an unconditional income. The right to a social security number, some paltry Welfare income and the ability to tell your friends that you live in the "land of the free, home of the brave" is not exactly much of a birthright.
My understanding when researching my own dual-citizenship is that you do not loose your American nationality when acquiring another nationality unless it was your intent to do so. Some countries require that you do this as a condition of nationalization (and some make exceptions for marriage, previous family ties, etc). So if you acquired a second nationality in a country that required this, knew that it meant giving up your US nationality, and willingly did so, you would no longer be American. Whether or you or the second country mention this to the US authorities is a totally separate matter, which can result in some interesting consequences later.
So if you need to renounce your previous citizenship as a condition of becoming, say, Columbian, then you would no longer be American (probably). Seeing as though he became Columbian through presidential decree, I'm guessing Columbia didn't make him do this. So now he is a dual-national, but from the US government's perspective he is American.
The problem is that you really don't want to be in a limbo state with your citizenship. Some politicians or bureaucrats in the future could decide that there are a lot of people abroad collecting social security, let's audit their citizenship.