I do not think this is limited to the same sex couple - heterosexual couples, even those married in the US, may experience similar problems, especially if they are of a "wrong" skin color. In fact, the INS scrutinizes all marriages quite closely (a marriage license alone is not enough, you must prove common residence, intimacy etc.) to ferret out those who married a green card. I am pretty certain, though, that if your friends were Dutch or British, coming back would not be such a problem.
Having said that - I am not arguing that right now same sex couples enjoy the same legal rights as heterosexual couples. In some cases they may enjoy similar rights (e.g. benefits) but that is the matter of good will of particular employers. But the argument "marriage or civil union" is mostly semantic, because state involvement in personal relationships is rather limited. The main form of that involvement is to guarantee certain property rights - and it does not go much beyond it. So as long as those property rights are guaranteed, the label, be it "marriage," "civil union" or, say, "shit on a stick" does not really matter. It is the people themselves who subjectively define what that relationship means to them - and if they want some sort of religious sanction of it, there are churches that do marry same sex couples (e.g. Unitarian-universalists).
I have been married three times, twice in Poland and once in the US, but in all three cases I needed to produce and sign legal documents needed to establish the legality of the marriage. After the court-administered legalities were completed, the involvement of religious figures of any kind was optional - for example the Commonwealth of Pennsylvania has a list of acceptable "MCs" - that includes but is not limited to clergy (e.g. a boat captain or peace officer will do). Needless to add that we did not use any religious services for that purpose.
So the bottom line is that this whole debate on same sex "marriages" vs. "civil unions" is mostly semantic and carried out by people for whom appearances are more important than substance. The state should guarantee same legal rights, including a right to enter a legally recognized relationship, to anyone regardless of sexual orientation. How that is union is called is matter of personal preference and semantics.
Wojtek