This is probably English, but is claimed as an Americanism until an earlier date than 1798 can be found. Shakespeare has My purpose is indeed a horse of that colour: Twelfth Night, ii. 3. (N.E.D.) A descendant of the Polk family says that his grandfather, writing at the time of Mr. Polks election to the presidency, said, they thought he would never win, but he proved a grey horse of a different colour. He adds that the phrase is common in the South, and the horse is always grey.
1798. Whether any of them may be induced to swear to support the cause of monarchy, or to enter into the pay of King John I. [President Adams] is a horse of another colour.The Aurora, Phila., Aug. 27.
1856. This identical issue is now presented, only the horse is of another color.Mr. Morrill of Vermont, House of Repr., June 28: Cong. Globe, p. 680, App.
1867. What did you think of his wife? Thats a horse of another colour altogether.Anthony Trollope, Chron. of Barset, i. 216. (N.E.D.)
1872. But, and he sighed heavily, this is a hoss of another color.J. M. Bailey, Folks in Danbury, p. 37.