Suche nach Umlauten funktioniert nicht

Hallo,

habe zur Zeit das Problem (wahrscheinlich seit einem Serverumzug), dass wenn ich im Frontend nach Worten mit Umlauten suche keine Seiten gefunden werden und die Umlaute im Suchfeld "verstümmelt" werden.

So wird z.Bsp. aus

ä = %25C3%25A4
ö = %25C3%25B6
ü = %25C3%25BC
ß = %25C3%259F

Suche ich allerdings im Backend (z.Bsp. in Alle Artikel) tritt dieses Problem nicht auf.
Auch sonst habe ich nirgends Probleme mit Umlauten (Permalinks usw.)


Ich verwende Wordpress 3.4.2 mit dem Atahualpa Version 3.6.4 Theme.
Weiters kommt PHP 5.3.13 und MySQL 5.1.63 zum Einsatz.

Im Theme ist

PHP:

Entschuldige, aber du musst dich registrieren oder anmelden um den Inhalt sehen zu können!

sowie auch fix charset=utf-8 eingestellt.
Und auch in Wordpress > Dashboard > Einstellungen > Lesen ist unter Zeichensatz für Seiten und Feeds UTF-8 eingestellt.

mfg
Tom