There was only one reason to ever think that nominal interest rates couldn't go negative, which is that the nominal return on both forms of base money (electronic reserves, and paper currency) had a floor of zero -- and investors wouldn't accept a below-zero nominal return when they could get a higher one by holding base money.
But for electronic reserves, there's certainly no practical need for a floor of zero: the central bank can easily pay negative interest on reserves. (For instance, the Swiss National Bank is now paying -0.75% on most "sight deposits", which is their term for electronic bank reserves.) It's quite easy: they just tell the computer to charge a certain amount of interest on reserve accounts, just as they would normally tell it to pay interest.
The potentially serious problem is paper currency, which by its very nature generally pays a nominal interest rate of zero. (If you have a \$5 bill, it will still be worth \$5 in a year - zero nominal interest.) The concern is that if we try to set nominal interest rates below zero, people will just massively switch to paper currency paying 0%, and the traditional financial system would disappear and be replaced by paper.
This is where we reach a very important point, which is that return isn't all that matters in an asset. Other factors, like convenience, play a role as well; different assets are convenient in different ways, and aren't perfect substitutes for each other. This is why in normal times, people are willing to hold paper currency even though it pays less than electronic accounts (because paper is useful in some ways that electronic accounts aren't); inversely, it's why in these abnormal times, when Swiss cash pays more than Swiss deposits, investors don't flock exclusively into cash.
Hence, when the SNB pays -0.75% on electronic reserves, rates in Swiss-denominated money markets (like the SARON overnight rate or LIBOR CHF) also drop to near -0.75%, and not everyone converts their electronic assets into paper. Indeed, there has been very little response on that front: if you look at SNB balance sheet column 16, banknotes in circulation, it hasn't budged very much thus far since negative rates began in December and the rates fell to 0.75% in January. Again, this is just a matter of imperfect substitutability: paper currency simply doesn't have the same kind of transactional and liquidity value that electronic accounts do. (And then there are the costs and risks of paper currency storage, as mentioned in the article you cite.) This is the feature of the world that wasn't adequately captured, before recent events, in the simple zero lower bound models used by many economists.
The one quasi-mystery, to me, is why banks haven't stockpiled paper. After all, even though an electronic account is more useful than paper to an end user, this doesn't apply to a bank that's already overflowing in electronic reserves. (Indeed, conceivably banks could be large-scale intermediaries here, stockpiling paper to back electronic deposits held by their customers - effectively transforming paper into a more convenient asset.) Yet the quantity of banknotes held by Swiss banks has remained low (see the 4th column at the bottom of the 2nd page here).
There are two possibilities here. One is that the logistical costs of holding cash are still higher than the 0.75% spread, so that it's still not worthwhile for banks to hoard. Another is that banks could make a profit by embarking on some large-scale cash hoarding program, but they know that the central bank would quickly get angry and create new rules (like a 0.75% tax on excess cash holdings by banks) to stop this, so they don't bother -- and indeed, maybe there has been under-the-table pressure from the central bank already!
Ultimately, when the government has the authority to regulate financial institutions, it can always disallow organized cash hoarding schemes that threaten the negative interest rate policy, so none of this is a long-term threat. The real issue is cash hoarding by end users - and there, the disadvantages of cash apparently still loom large at -0.75%.
(One complication, by the way, is that I think banks are generally not charging negative interest on small-scale retail deposits. At least superficially, then, the relevant interest rate isn't negative for the typical consumer; but I suspect that banks are making up the difference by charging fees, etc., which is already necessary to recover their costs even when interest rates are at 0%. For large-scale deposits, on the other hand, banks are charging clients to hold cash - and, of course, this must be true, since money market rates wouldn't be negative if it was always possible to find some bank that would give you a zero rate.)