When has an organism evolved enough to be called a new species?
I think LuketheDuke's answer is an oversimplification of the biological species concept (possibly resulting from the dictionary having a poor definition). The definition he gives is one of many which are in current use, and is made redundant by many types of organism.

It is important to recognise that because reproduction is not the same process in all organisms, genetic differentiation between individuals occurs in different ways for different groups.

Let's take the definition given in LuketheDuke's answer...


  The major subdivision of a genus or subgenus, regarded as the basic category of biological classification, composed of related individuals that resemble one another, are able to breed among themselves, but are not able to breed with members of another species.


Under this definition, lions and tigers (see ligers and tiglons, which are sterile hybrids between the two) would be considered one species, as would donkeys and horses (see mules and hinnys, again sterile hybrids). There are hundreds of other examples of pairs of animal species which can hybridise to produce sterile offspring.

However, these animal hybrids usually only take place with human intervention, by delibrate breeding efforts. Thus we could extend the previous definition to include them...


  The major subdivision of a genus or subgenus, regarded as the basic category of biological classification, composed of related individuals that resemble one another, are able to breed among themselves, but do not breed freely with members of another species in the wild.


That last part takes care of the ligers and tiglons. But what if we consider plants? Under the definition I just gave, most grasses (around 11,000 species) would have to be considered as one species. In the wild, most grasses will freely pollinate related species and produce hybrid seed, which germinates. You might then think we could just modify the definition to specify that the offspring must be fertile (i.e. able to reproduce with one another)...


  The major subdivision of a genus or subgenus, regarded as the basic category of biological classification, composed of related individuals that resemble one another, are able to breed among themselves, but do not breed freely with members of another species in the wild to produce fertile progeny.


Unfortunately, the situation is still more complicated (we've barely started!). Often wild hybridisation events between plants lead to healthy, fertile offspring. In fact common wheat (Triticum aestivum) is a natural hybrid between three related species of grass. The offspring are able to breed freely with one another.

Perhaps we could account for this by taking into account whether the populations usually interbreed, and whether they form distinct populations...


  The major subdivision of a genus or subgenus, regarded as the basic category of biological classification, composed of populations or meta-populations of related individuals that resemble one another, are able to breed among themselves, but do tend not to breed freely with members of another species in the wild to produce fertile progeny.


This accounts for the grasses, but it still leaves a messy area when you have a hybridisation which establishes - until the hybrid population is segregated away from the parent populations it is unclear whether they still count as the same species.

We could probably live with this situation, except for the fact that bacteria refuse to conform to it at all. Bacteria of the same species, or even very different species, can freely transfer genes from one to the other in conjugation, which combined with fission can result in perfectly replicable hybrids. This is such a common occurence that it breaks even the 'tend to' part of the previous definition, and members of a population can be doing this almost constantly, which negates the segregation requirement.

Richard Dawkins had a go at defining around this, by stating that...


  two organisms are conspecific if and only if they have the same number of chromosomes and, for each chromosome, both organisms have the same number of nucleotides 


This partly gets around the bacterial problem and means that bacteria which result from conjugation are a new species. Unfortunately under this definition we might as well not ever bother trying to classify bacteria as billions of new species would be created every day - something which the medical profession might have something to say about. This definition would also mean that those with genetic diseases like trisomy 21 are not human. The final nail in the coffin of this attempt is that there are many species, including frogs and plants, which are very certainly considered a single species by taxonomists but which have some variety in the presence of small accessory chromosomes, which occur in different combinations between individuals.

Let's consider one last option. We now live in the era of genomics where data about genomes of thousands of organisms is accumulating rapidly. We could try to use that data to build a species definition based upon similarity at the nucleotide level. This is often used for bacteria, by considering organisms with less than 97% nucleotide similarity to be different species.

The major point I've been trying to make, though, is that species is not a natural concept. Humans need to be able to classify organisms in order to be able to structure our knowledge about them and make it accessible to people trying to link ideas together. But the natural world doesn't care about our definitions. Ultimately the species concept is different for different groups of organisms and will continue to change over time as our analytical methods and the requirements of our knowledge change. Note that I've deliberately skipped over many historical species concept ideas.

The direct answer to your horse question is "it depends how you want to define a horse".