As a former ICPC world finalist who later worked at Google, I would say that practicing for programming contests is almost like cheating as far as Google interviews are concerned. The Google interview format is almost identical to the ICPC practice sessions I did in college.
I've seen this video before, and IMO the extreme similarity between programming contest questions and Google interview questions could explain the negative correlation. Specifically, borderline engineers with programming contest experience are more likely to get hired than borderline engineers without programming contest experience, and therefore the set of Google engineers with programming contest experience includes more borderline people than the set of Google engineers without programming contest experience. Thus the slight negative correlation.
When I was in high school, being good at programming contests meant picking up a bunch of habits that you'd never use at work -- memorizing the same twenty #include lines that include every conceivable STL data struct you'd need; using single letter variable names; no comments whatsoever. If you and the next person come up with the solution at the same time, you might lose simply because the other person could type faster. You have to un-learn these habits for industry.
Just about anyone can get exposure to a set of representative coding questions (see: the USACO training robot, or Cracking the Coding Interview), but training for these contests means spending XX hours a year under a time limit trying to write code from memory (because you don't have time to look things up in the manual).
I expect this to be the true root cause of the negative correlation as well. Technical questions are good at rooting out those not good at data structures and algorithms, and good at promoting those that do. However, you can be excellent at solving ICPC questions and not know anything about documentation, object oriented design, OS, databases, anything web related, etc. It's a very specific skill and practicing programming contests optimizes for it.
I've seen this video before, and IMO the extreme similarity between programming contest questions and Google interview questions could explain the negative correlation. Specifically, borderline engineers with programming contest experience are more likely to get hired than borderline engineers without programming contest experience, and therefore the set of Google engineers with programming contest experience includes more borderline people than the set of Google engineers without programming contest experience. Thus the slight negative correlation.