They may not have experienced such, but threading presented this way was already a well-established thing before gmail. Not so much with email as with newsgroups, but still.

Also, some people considering a problem "hard" is an entirely different thing than a problem being widely considered as "impossible". This was not anything close to an impossible problem.