Well I'm an idiot - the fulltext index on page_text was missing from a default installation. It didn't break searches but probably slowed them down tremendously. Also set engine to MyISAM on page_text to avoid cryptic error messages from MySQL.
Beginning with version 2.0.5 the language packs are no
longer included with the core distribution.
Language packs can be downloaded from the TinyMCE website:
http://tinymce.moxiecode.com/download.php
The language pack codes are based on ISO-639-1:
http://www.loc.gov/standards/iso639-2/englangn.html
Plrease try using entities if possible. Like å etc for non a-z characters.