The Grelling-Nelson paradox, according to the Penguin Dictionary of Mathematics (2008) is:
A paradox stated by K. Grelling and L. Nelson in 1908. An adjective is called autological if it has the property denoted by itself. Thus the word 'English' is an English word, 'short' is short, and 'polysyllabic' is polysyllabic. If an adjective is not autological, it is heterological. Thus 'German' is not German, 'long' is not long, and 'monosyllabic' is not monosyllabic. What of the word 'heterological' itself? Is it heterological? It must be either autological or heterological. (p. 201)
This, I think, is a similar type of problem in the Godel Proof that says that any axiomatic system will have the capacity to generate undecidable statements, and, the corollary, that the consistency of a formal system containing arithmetic cannot be proved by the said system.
Not being a mathematician, and only as a language analyst, I can say that the Grelling-Nelson paradox is rather Anglocentric, and a superficial one at that. And I've never been able to totally accept Godel's Proof for the simple fact that there are these things called "linguistic accidents" like little, green ideas dream furiously.
The Grelling-Nelson paradox is too highly language-specific to be a real paradox within a formal system. It does not consider the real possibility that a given language may have a completely different grammatical structure such that it invalidates their insights completely. For instance, in mathematics alone, one may denote extremely large and extremely small numbers by way of scientific notation: are these numbers autological or heterological? -the question is totally meaningless. In linguistics, the word 'English' may also be denoted as 'Anglophone'; is the word 'Anglophone' English?
If we accept that the word 'Anglophone' is English - and it means 'the English language' in many linguistics textbooks - how do we use the terms autological vs heterological in any productive way?
Now, the Godel Proof, I've read in many maths books that I own that there is often more than one way of constructing a proof. The great Gauss did it all the time where he'd reformulate a statement and his line of reasoning would come out more beautifully and elegantly than other people's proofs. Selberg did the same thing when he and Paul Erdős had a dispute over a certain proof where he was able to bypass Erdős' insight completely.
In the area of physics, it is said that Feynman had an unconvention take on physics, and as a kid he had his own notational system drastically different than the symbolism of maths.
These things are possible because a purely text-based critique (ie, mistaking the text for conceptual level structures) is just so replete with linguistic and logical pitfalls that are often more apparent than real.