Pureblood status was irrelevant to the majority of witches and wizards. To those who it did matter to something as inconsequential as having a Muggle-born mother would be more than enough to "taint" you, likely for multiple generations. The "best" you could hope for, if you actually cared, is to be Half-blood.
Of course, in practice the application of these "rules" is inconsistent at best. Families like the Malfoys were more than willing to serve Lord Voldemort, whose father was a Muggle (not even a Muggle-born wizard). I'm sure Ministry officials like Dolores Umbridge - during the period when Voldemort controlled the Ministry of Magic - would have been more than willing to trade "Pureblood" status for valuable information (I can't remember if there's any hard evidence for this in the books, though).
Blood status in the Harry Potter books has huge parallels with the Nazis treatment of the Jews. There's a famous quote from a high-ranking Nazi (I believe it was Hermann Goering) that goes "I decide who is a Jew."
The same applies here, I think: Harry is a Half-blood because the people blood status matters to said so.