Whenever Piwik gets slow you will have to setup cron archiving: http://piwik.org/docs/setup-auto-archiving/
By default, Piwik will aggregate data when you a) make an API request - b) Load the dashboard (which in fact calls the API). Cron archiving makes this process faster by processing all the data beforehand so that the API can simply request it from the DB.
I've got a site that is receiving nearly 10,000 daily uniques since Google's last [panda|penguin|whatever] update in May, and while Piwik's performance was not terrible, setting up the cron a few weeks ago made the whole experience very snappy.
Thank you for your work halfdan!
See here: http://piwik.org/log-analytics/how-to/
Edit: It should be noted that you will get lots of bots requests showing up when you load access logs (the regular tracker relies on javascript, which gets rid of most of the bots). I have a small awk script that cleans the access logs prior to importing them, by trying to detect bots. I can upload that if you're interested.