There is a huge difference in the amount of keywords that piwik records compared to awstats or clicky, google, etc.
So I had a look at what was in the database and I saw that most referer URLs were stored encoded.
It probably won't show on here, but let's try:
The ones that weren't encoded, generated the proper info in Piwik.
I thought it could be some server permissions or filter, but why would it work with some visitors only?
This appears to be a symptom of #1747. Marking as a duplicate unless determined to have a different root cause.