It's a matter of definition, and
hearkens back is similar to the 'One drop Rule' that used to be well known in the US. Basically, to be a pureblood, you must come from magical families on both sides, not just two magic-using parents. Conversely, any muggle blood makes you 'half-blood' at best.
"The term 'pure-blood' refers to a family or individual without Muggle
(non-magic) blood. The concept is generally associated with Salazar
Slytherin, one of the four founders of Hogwarts School of Witchcraft
and Wizardry, whose aversion to teaching anybody of Muggle parentage
eventually led to a breach with his three fellow founders, and his
resignation from the school."
None of the families are really pure-blooded, as Dumbledore points out in Beetle the Bard
"So-called pure-blood families maintain their alleged purity by
disowning, banishing, or lying about Muggles or Muggle-borns on their
family trees. Then they attempt to foist their hypocrisy upon the rest
of us by asking us to ban works dealing with the truths they deny.
There is not a witch or wizard in existence whose blood has not
mingled with that of Muggles..."
Harry's Mother's family is not a recognized wizard family, so he has muggle-blood. Any muggle-blood with wizard blood defines him as a Half-blood.
To go straight to the horse's mouth, here's JK Rowling on the subject:
(Note: This is from the Harry Potter Wiki, and I haven't been able to substantiate it as an actual JKR quote yet.)
The expressions ‘pure-blood’, ‘half-blood’, and ‘Muggle-born’ have
been coined by people to whom these distinctions matter, and express
their originators’ prejudice. As far as somebody like Lucius Malfoy is
concerned, for instance, a Muggle-born is as ‘bad’ as a Muggle.
Therefore Harry would be considered only ‘half’ wizard, because of his
maternal grandparents. If you think this is far-fetched, look at some
of the real charts the Nazis used to show what constituted ‘Aryan’ or
‘Jewish’ blood...the Nazis used precisely the same warped logic as the
Death Eaters. A single Jewish grandparent 'polluted' the blood,
according to their propaganda.