I would like to present a different analysis of most of the same facts mentioned in the other answers.

While I am normally skeptical of post facto authorial statements, especially with this author, in this case I think it is reasonable to accept that it is not an invention that was conceived after the story was completed.

Let's begin with the three points of criticism in Gareth's answer:

“I knew that Thestrals were coming and I can prove that because they’re in the book” — the second part (“I can prove that”) is false: the appearance of the Thestrals in Fantastic Beasts doesn’t prove that Rowling had decided to use them in future novels. (There are plenty of entries in Fantastic Beasts that went unused.) The falsehood in the second part casts a bit of doubt on the truth of the first part.

When Rowling said "I can prove that", I don't think she was being as precise as assumed. Indeed, being mentioned in a book is no proof that they will be used in a different book. However, what I suspect she meant is that the existence of Fantastic Beasts proved that she didn't entirely invent the concept of Thestrals when writing the Order of the Phoenix, but had already thought of the concept prior to writing Goblet of Fire.

Alternatively, and approaching this from a somewhat psychological perspective, I would argue that this very assertion of proof is itself (some amount of) proof. If she was lying (or misleading, if lying is too strong of a term for this context) she would know that her proof was not a good proof, and therefore would likely not offer it since it could be easily refuted. The fact that she did offer it seems indicative of the fact that she herself believed it, which would only be the case if the concept was not a retroactive invention.

“However, if Harry had seen them and it had not been explained then it would cheat the reader” — this concedes that she had not anticipated using Thestrals, so that introducing them appears to contradict what she wrote previously, hence the need for an explanation.

I'm not sure if I am interpreting this paragraph correctly but it seems to be assuming that Rowling meant that introducing Thestrals without explaining how it is consistent with previous information in the books would be cheating the reader, and is thus an acknowledgment that the description of Thestrals is inconsistent with the earlier story. However, I don't think that is what Rowing meant here. I think she meant that introducing a new concept (Thestrals) without explanation of the concept (since it would have been the end of the book) would be cheating the readers. Under this understanding there is no acknowledgement of inconsistency.

“that’s how I’m going to sneak past that one” — the use of “sneak” is a suggestion that there is something furtive or shameful about her approach. I interpret this as a (humorous) admission that the way she answered the question is misleading.

I don't think "sneak" here is referring to the manner in which she answered the question, but to the unsatisfactoriness of the answer within the context of the story. That is to say that it is not an implicit admission that she retroactively added something, but an admission that in order to keep the flow of the books she had to (from the outset) create an unsatisfactory explanation of the concept.

Now let's turn to why I think we should give some credence to Rowling's assertion. First we have the original quote from Prisoner of Azkaban (cited in Gareth's answer) in which the pulling of the carriages was described as "Harry could only assume, by an invisible horse". If you think about it this seems like a rather strange assumption for Harry to make. In a world of magic why would you assume that carriages moving of their own accord are being pulled by horses, which not being seen must then be assumed to be invisible? Why not just assume that the carriages move magically? At this point in the story Harry has already seen several examples of vehicles moving without anything physical pulling them, including Uncle Vernon's boat (bewitched by Hagrid), the Gringott's cart, the boats for crossing the lake at Hogwarts, Mr. Weasley's car, the Durmstrang ship, broomsticks, portkeys etc. On none of these occasions does Harry assume, or even entertain the possibility, that the motion is actually caused by invisible creatures. Thus, the mention of invisible horses in Prisoner of Azkaban would seem to be entirely gratuitous.

I suspect, therefore, that Rowling deliberately included this (despite it being somewhat odd in context) precisely because she already had the idea that the carriages were in fact pulled by invisible horses. The passing thought by Harry was intended as a harbinger of what was to come later in the story.

This can also help address another issue, mentioned in Gareth's answer:

In Goblet of Fire (2002), the stagecoaches have become “horseless carriages”, with no mention of the theory that they are pulled by invisible horses:

To this we could say that there was no need to reiterate Harry's invisible horse theory since the "clue" had already been given and it was already odd to mention it the first time.

There is another seemingly gratuitous line which can also support the case here. In Fantastic Beasts Thestrals are described as unlucky (more precisely that some people consider them unlucky. No reason is given for this unluckiness, so why mention it at all? Presumably, then, this is another hint to the death-seeing criterion, which is after all the reason why they are considered unlucky (as explained in Order of the Phoenix). The reason for not mentioning anything about death in Fantastic Beasts is then readily apparent: she didn't want to spoil a plotline of a future book.

Another apparent omission by Fantastic Beasts, mentioned in Gareth's answer, is:

Note that there is no mention of any types of winged horse being employed to pull carriages, something which I think we would expect to see if Rowling had already had the idea; compare “griffons are often employed by wizards to guard treasure”, “Jobberknoll feathers are used in Truth Serums”, etc.

However, I this can be reasonably explained within the context of the story. In Chapter Twenty of Order of the Phoenix we find the following passage:

“But tha’s not very interestin’, Hermione,” said Hagrid. “The stuff I’ve got’s much more impressive, I’ve bin bringin’ ’em on fer years, I reckon I’ve got the on’y domestic herd in Britain —”

It is thus reasonable that Fantastic Beasts does not mention that Thestrals are used for pulling carriages, as prior to Hagrid's herd it may never have been done.

Perhaps further support for believing Rowling comes from the fact that her answer did not actually address the question asked. As cited in Rand's answer, the interviewer asked her why Harry couldn't see Thestrals the entire time since he had seen death as a baby, not why he couldn't see the Thestrals after witnessing Cedric's death. In her answer Rowling only discussed why he couldn't see them after witnessing Cedric's death, without mentioning the baby aspect at all. Indeed her response does not directly resolve the baby question, unless you extrapolate and take the idea further, as in Rand's answer, and argue that not understanding the concept of death would be an impediment similar to not processing a death.

However, if Rowling had indeed had the idea of Thestrals all along, and had created the answer when writing the book originally, then it makes sense why she answered in this way. She had previously thought about the inconsistency with Cedric so that was the first thing that would come to mind when being asked a question about the inconsistent nature of Thestrals. She likely had not previously thought about the inconsistency with baby-Harry, and indeed one could argue that that inconsistency still stands.