"Colour me (something)" means the same as "call me (something)", typically, "colour me stupid" or "colour me gone".
Green's Slang Dictionary has "color" (US) as "to see, present as", and the first citation is for an advertisement for a television series (I'm Dickens He's Fenster) in 1962 "Color her married".
The first definition in the OED is specific to diamond mining, where an off-colour diamond is neither pure white or another colour, which makes it of inferior value (there are quotations using the phrase from 1860 - 1968).
The next definition is more general and has two sub-definitions. The first means of a colour that's either darker, lighter, not natural, proper or acceptable (quoted 1873 - 2000). The second is to be slightly unwell, or not up to the mark, or out of order (1876 - 1997).
Finally, the third is what we're after:
Of questionable taste, disreputable; improper, vulgar; spec. (of language, jokes, etc.) slightly indecent or obscene. Cf. dirty adj. 2.
The first quotation:
1875 J. G. Holland Sevenoaks in Scribner's Monthly Mar. 582/1 Everybody invited her, and yet every body, without any definite reason, considered her a little ‘off color’.
Searching Google Books, I found some antedatings. First for diamond mining:
The Mirror of Literature, Amusement, and Instruction - Volume 5 - Page 15 - John Timbs - 1825:
The smallest flaw, or foul (as it is called) greatly diminishes the price of the diamond; and if it be tinged with yellow, brown, &c., a fault characterised by the technical term off colour, its value falls very considerably, and is frequently reduced from a third to one half.
Next, for a general use (though I'm not sure if this means "unwell" or "of questionable taste"):
Paris in '67: Or, The Great Exposition, Its Side-shows and Excursions - Page 87 - Henry Morford - 1867:
... and yet, though I have no doubt that the lady has been a little 'off color,' and though Mazeppa and the French Spy may not be exactly the thing in which we should like our sisters to 'show themselves' — yet, do you know, I am not only in love, ...
Best Answer
The earliest use, according to the OED, seems to have been in 1860 in the diamond industry, where it described a diamond that was ‘neither pure white nor any definite colour, and so of inferior value.’
Thirteen years later it was used to mean ‘Not of a colour considered natural, proper, or acceptable; paler or darker than expected or usual.’ Three years after that was in extended use to mean ‘Not in good health, slightly unwell; (also) not up to the mark, defective, deficient, out of order.’
Around the same time it was also in use to describe something that was ‘Of questionable taste, disreputable; improper, vulgar; specifically (of language, jokes, etc.) slightly indecent or obscene.’