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 

http://community.elgg.org/mod/groups/topicposts.php?topic=220244&group_guid=12

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?