The reason why Newtonian thought is insufficient for GPS devices is because it cannot account for the components intrinsic to the very fabric of reality itself, namely the the analogous relation between space & time, known as the space time continuum. Newton thought only in terms objectified as objects. Einstein's thinking was different, he didn't think in terms of discrete objects, but RELATIONS.
Einstein's thinking is embodied in this picture of Earth depicted relative to the space/time continuum (relation).
A complete explanation of Einstein's achievement is given in this article, it explains how a shift in thinking from discrete objects (Newtonian) to relations (Einstein's concept of relativity) helps account for GPS devices (satellites).