A couple possibilities:

-Your grandfather's grandmother was not actually Native American.

-Your grandfather's grandmother was not actually his biological grandmother.

DNA can be lost over generations, but if someone's grandparent is 100% [insert ethnicity here], that ethnicity is going to show up in their DNA. The only other thing I can think of is that there's something wrong with Ancestry.com's prediction of Native American ancestry - if a whole bunch of people with clearly documented recent Native American ancestry were not seeing that in their results, maybe. But I haven't heard of that happening, and I think the two scenarios I mentioned above are more likely. Good luck solving your family mystery! :)