Tags with non-ascii (international) characters don't work after upgrade to version 1.6

After upgrading from version 1.5 to 1.6 clicking on tags with non-ascii characters yields no results (was ok in 1.5).

First after the upgrade tags didn't work at all but after applying the .htaccess fix from 


then tags only with letters from the English alphabet do work as expected but tags with letters as áéóúíðþæö still don't.

What might be causing this and how can I fix it?