El punto es que también debes cambiar todos tus enlaces para que funcione por completo, no basta únicamente con activar mod_rewrite.
Me refiero a que debes cambiar de esto:
Código HTML:
<a href="foo.php?candy=bar">link</a>
A esto:
Código HTML:
<a href="/foo/bar">link</a>