The special page was rewritten in MediaWiki 1.23 to make it usable on
wikis the size of Wikipedia (commit 87be24db /
and some follow-up changes).
Unfortunately this optimization for massive wikis seems to have caused the
performance to suffer on smaller ones a bit.
(I have no answer to your problems, just saying this. :( Perhaps it helps
someone else help you.)