Maybe it would make more sense to choose the 65,536 most common English words (or whatever language you want) and break the address up into 8 words to form a crazy looking phrase. This is still difficult to memorize but not as bad as just stuffing 128 bits of hex down your throat. You could even allow for the collapsing 0s by making entry 0 be "and" and adding a bit of logic that does the collapse.
For fun I wrote a tiny script that does this and tried it with their example domain:
1234:5678:9abc:def0:1234:5678:9abc:def0 -> balcony gaining pawn toothill balcony gaining pawn toothill
Or Google's address from that page:
2a00:1450:4009:811::200e -> chinker bauchle dorter amor and bromidic
So maybe this wasn't the best idea, but at least they're a bit more amusing than the hex noise in the article.
Anyway, if anybody else wants to play around with it I have a tiny demo: http://jubei.ceyah.org/cgi-bin/ipv6toenglish