I always thought puce is purplish, perhaps because the Welsh word piws (pronounced "puce") means purple.
The word entered English from the French, where it had become a fashionable colour amongst the French aristocracy. The earliest OED citation in French is 1775, and in English is 1781 for the noun and 1787 for the adjective, but I found an earlier English example.
In the 1779 epistolary novel The Sylph, published anonymously by Georgiana Cavendish, Duchess of Devonshire, the protagonist appropriately describes confusion with new and unfamiliar colour names:
I have had a thousand patterns of silks brought me to make choice and such colours as yet never appeared in a rainbow. A very elegant man, one of Sir William's friends I thought, was introduced to me the other morning.-I was preparing to receive him as a visitor; when taking out his pocket book he begged I would do him the honour to inspect some of the most fashionable patterns, and of the newest taste. He gave me a list of their names as he laid them on the cuff of his coat. This you perhaps will think unnecessary and that, as colours affect the visual orb the same in different people, I might have been capable of distinguishing blue from red, and so on; but the case is quite otherwise; there are no such colours now.
"This your ladyship will find extremely becoming - it is la cheveaux de la Regne; but the colour de puce is esteemed before it, and mixed with d'Artois, forms the most elegant assemblage in the world; the Pont sang is immensely rich; but to suit your ladyship's complexion, I would rather recommend the seuile mort, or la noysette".
Fifty others, equally unintelligible, he ran off with the utmost facility.
I've no idea why some people think puce is greenish, but I did find this from an 1811 The Medical and Physical Journal:
In general, imperial tea is deep green, green tea is puce green, hyson is blueish green, bohea is yellowish green, peko is almost black, gunpowder tea is greyish green, souchong is reddish.
This isn't necessarily saying puce is green; it's saying this green tea is coloured green with a hint of puce (whatever colour puce is).
I expect the confusion is much older, but puce has been mistaken at least in 1992:
I said. "Nobody could pee that much. A beautiful color, puce." "Puce is pink, not yellow," Abdhul said.
And in 1995:
... Most people describe it as an icky yellowish green, when it's actually a reddish brown.
NW: Could that be because puce sounds like puke, so we think of vomit?
LE: Probably. There is something more than slightly odoriferous about the way the word sounds. But there's an alternative name taken from Old English that sounds even worse: pewke.
NW: Whereas puce comes from the French for "flea"?
LE: Right. That's how to remember that puce is a reddish brown — it's the same color as an engorged flea belly.
NW: That's kind of up there with puke. "Oh, I love this dress! It's the color of an engorged flea belly."
LE: Not a pretty picture, is it? We'd swear Wuthering Heights is one ...
And possibly in 1988:
Also, one needs some code to run at the outset that insures the color table
is the way you like it when you start up Smalltalk, or after you've done
something else, your pretty sky blue Browser label may have turned a sickly
puce!
The only explanations I've found involve mistaking puce for a puke green.