Just encountered the phrase “men of color” in an 1857 article about the Dred Scott case from the Albany, NY Evening Journal.
I could have sworn that there was a discussion about the history of the phrase “people of color” in my blog, and that Dominus (I think?) gave a very early cite, but now I can't find that. I did find an entry from 2002 in which I noted that I had just found a 1971 use of the phrase, but it turns out to go way further back.
Wikipedia now has info about the history of the phrase, but that info isn't necessarily accurate. But the article does cite a 1988 William Safire column that cites “a 1793 pamphlet about a yellow-fever epidemic” as an earliest known source.
(Safire also notes that Martin Luther King used the phrase “citizens of color” in his 1963 “I have a dream” speech.)
I also ran into the Wikipedia article on free people of color, a phrase that apparently derives from the French gens de couleur libre. The article is about the people rather than the phrase, and it's a little short on dates, but if I'm not reading too much into it, it implies that at least the French phrase was in wide use in New Orleans and the Caribbean well before 1810.
As far as I can tell, from reading histories of the Haitian Revolution, "gens de couleur" was a term in common use from very early in the history of the Saint Domingue colony, and certainly well-established by the mid-1700s.