Resolvi aqui sozinho mexendo mesmo.
O Problema não tem nada a ver com o category.php.
Eu tenho um menu na sidebar com links para as categorias. O menu que estava com links errados.
Por exemplo:
<a href="<?php echo get_option('home');?>/massas
ao invés de:
<a href="<?php echo get_option('home');?>/category/massas
Então o link para página ficava errado. Bastou adicionar /category/.
Assim deu certinho com links permanentes.
