Você tem acesso ao httpd.conf? Em caso afirmativo, por favor, adicione ao httpd.conf:
RewriteLog "/tmp/mod_rewrite.log"
RewriteLogLevel 3
E poste o que esse log diz quando você carrega /category/2 . Remova isso depois de obter as informações necessárias - é um desperdício de recursos do servidor.
EDITAR:
Obrigado pelo log. Algo está reescrevendo o URL para: /category.php/13 . Qualquer outro RewriteRules? Você está usando o FastCGI? E se você renomear category.php para outra coisa, como Category.php ou display_category.php ?
EDIT2:
Como algo parece estar reescrevendo /category/(.*) para /category/$1 e não sabemos o que é, por que você não muda:
RewriteRule ^category/([^/\.]+)/?$ /category.php?category=$1 [L]
para:
RewriteRule ^category.php/([^/\.]+)/?$ /category.php?category=$1 [L]
e veja se isso funciona?