Neither the Declaration of Independence nor the Constitution allow for the recognition of gay marriage. Of course, they don't allow for the recognition of any marriage. I'll be willing to bet Canada's situation is similar.

Therefore, I propose that the solution to the gay marriage snafu is for the government to stop recognizing marriage altogether. It's just not something they need to be doing. If two heteros, gays, lesbos, or potted shrubs wish to go to a church and give vows to each other, so be it; it won't change their status in the eyes of the government any. Just give all tax breaks and such that apply to married people, to everyone...

Of course, the answer won't be quite that easy, but I think it could be a good start. Unfortunately, in the immortal words of Bill Watterson's Calvin, "A good compromise leaves everyone mad."