We're generally free from government suppression of speech, but not free from the social consequences of that speech, because we're also all free to choose with whom we associate and in what manner.
In other words: Many things are legal and still reprehensible.
I can't fix the Internet, but our discourse would likely be improved by people speaking online with the same care they are likely to apply in person. Or perhaps having auto-lockout on your twitter account when you're drunk. ;)
I don't want to belabor this because Garry has (rightfully) apologized, but I would hope that the standard public figures hold themselves to is “does this elevate the level of discourse”, not just “is it legal to say this”. Things that could not-unreasonably be construed as death threats do not meet that standard.
Threats are not always legal. You can argue that it wasn't a threat, but you'd be wrong. Wishes from people in authority are often seen as calls to action by others. Even that's not what he intended, it's would still rightfully be seen as threatening by the target.