From the idiomatic expression "That's a horse of different color." meaning "That's completely different."
Origin
My purpose is, indeed, a horse of that colour.
The more reasonable source is Shakespeare's Twelfth Night (1601) where the above line appears. In short, it means "Yes, that is my plan."
Whether any of them may be induced to enter into the pay of King John I is 'a horse of another color.'
The above line appeared in the Philadelphia newspaper Aurora in 1798, taking a shot at President John Adams. That form is very similiar to that in the title of this node.
Both of those uses probably originated from horse racing or horse trading.
One theory is that the intended image is that of watching a horse race, looking away for a moment, and, to one's surprise, returning to see that a horse of a different color is in the lead.
The other theory is that a horse, when sold, may not have the same color hair as was registered at birth. This may be natural, or there may be another reason.
Notable Use
Shortly after the aforementioned phrase is said in The Wizard of Oz in the magical Emerald City, a horse-drawn carriage appears led by a "horse of a different color," which is a different color in every shot. For example, it might be green in one shot and red in the next shot a few seconds later. This was the first movie special effect ever done in color.
Sources:
http://www.takeourword.com/et_h-j.html#horseofa
http://www.phrases.org.uk/bulletin_board/22/messages/246.html
http://members.aol.com/MorelandC/HaveOriginsData.htm