>>>"a real-world example of Godel's theorem..."
>>>"So cool to find out that logic alone is not enough."
In my limited view the problem Godel brought to light with his Incompleteness Theorem was that math itself (and thus logic, as you point out) is imperfect. Specifically, a mathematical set will always be capable of generating problems that it cannot resolve without amending itself. Once this new set exists, it will be capable of generating a new problem beyond its own reaches... a vicious circle, for sure. It was my (and others') big contention with Alexander, who claimed math was 'perfect,' but who hasn't been around for ages.
Yours is a neat example; another good "layman's" example is the idea of infinity. Infinity can only be explained within a larger paradigm, making the concept a paradox.
There are two ways we can consider an infinity: we may either explain it in logical terms, or suppose that it can never be explained in logical terms. Germane to the second example is the problem that its premise and its conclusion are one in the same -- both pure inference -- and thus just a buig, fat guess. But with logic we can play with the first idea -- a mathematically explainable 'infinity.'
SO, take a circle -- which is an 'infinite' line. The line is only boundless once a second dimension is introduced... making the line no longer infinite. Boundless, but quite finite. Add a dimension to this concept, and we find ourselves considering the plane. An 'infinite' plane becomes merely boundless once we see that it can exist -- within a logical framework -- as the surface of a sphere. We've extended the playing field in order to work out our mathematical quirks, reducing the 'infinite' plane to a mere finite, though boundless, area.
Simple, I know, but I love that you brought these Godel-parallels to the table!