Russel countered with his Theory of Types, but it was thoroughly unsatisfactory and you could tell his heart wasn't in it. That idea essentially ruled out self-reference; that is, metastatements of the order of "this statement is false" were illegal. But in fact there turned out to be no reliable way of deciding where the boundary between statement and metastatement really lay; in fact, there isn't one, as Russell concluded himself.
But that does not invalidate logical systems per se, as the postmodernists fervently believe, it simply dictates that they have boundaries. It does not state that there is no truth or logic, or that all points of view are therefore equally valid, quite the opposite, in fact. It simply states that formal logical systems have limitations. Most adults should be able to live with that.
What Godel showed was twofold: first, that within any formal logical system of sufficient power, a statement could be made that was true but undemonstrable (incompleteness) and second, that a statement could be formulated following that system's rules that could be shown both true and false (incoherence).
Two (friendly) comments. First, it's important to say "undemonstrable within the system" rather than simply "undemonstrable". Second, it's not quite accurate to say that "a statement could be formulated following that system's rules that could be shown both true and false (incoherence)"—if that were true, the system would be inconsistent, which nobody desires. The aim of the constructor of a formal logical system is to rule out the possibility of contradiction, but at the same time to insure the possibility of proving the greatest number of true propositions. What Gödel showed was that if a system has the expressive resources needed to formulate the axioms of natural number arithmetic with multiplication, then it is impossible to prove within the system every true proposition without incurring the penalty of inconsistency, i.e., the ability to 'prove' a contradiction (such as, 1=2). Since no formal system constructor wants an inconsistent system, (s)he's forced to give up the hope of being able to prove every true proposition within that system.
In short, in a 'strong enough' system, the penalty for completeness is inconsistency, and the penalty for consistency is incompleteness.
Of course, by expanding the system to include new axioms, propositions which were previously known to be true but unprovable, become provable. But, again, in the expanded system, new propositions can be formulated which can be known to be true, but turn out to be unprovable within the expanded system. And so on ad infinitum.
Note that Principia Mathematica used both "and" and "not" as a complete system. Somehow, Russell and Whitehead missed out on using the Sheffer stroke ("nand") or "nor." Either of these would be more minimal than PM's usage but equally difficult to read. More modern logic books use at least: and, or, not, implies, equivalent, and some add nand and nor.