I have the same problem since the update. Not using a custom directory or filename.
I fixed the error by removing from functions.php
$wp_rewrite->flush_rules();
Also I disabled simple tags plugin.
Now category permalinks works fine on:
http://www.maniadecelular.com.br/cat/modelos-celular
