mod_rewrite is not my strong suit so i cant really offer a lot of assistance on this one, you would probably get better help posting to the webmaster world forums or another forum more specific to mod_rewrite.
however, i think you need a leading forward slash in your rule:
RewriteRule ^([^/.]+)/?$ category.php?Categories=$1 [NC]
RewriteRule ^([^/.]+)/?$ /category.php?Categories=$1 [NC]