Harry, a half-blood?

[american_pie8887]

No: HPFGUIDX 68836

OK when Dumbledore speaks about the prophecy, it's mentioned that 
Harry might've been chosen over Neville b/c he's a "half blood" like 
Voldemort was and Neville is  a pureblood. Maybe i'm totally lost 
here, but doesn't having both magical parents make someone a 
pureblood? Both James and Lily had magical powers, so why is Harry 
considered a half blood? I also know that Lily was a "mudblood" so I 
dont know if that affects what Harry is or not! Anyone out there with 
another opinion? I'd love to have some answers!!
~Mags