Well if standard Joomla SEF does not work either with mod_rewrite on, then this is not a JoomSEF problem. You need to check your .htaccess file, usually there is a problem with RewriteBase directive, if you're developing your site locally and you have it in some subfolder, like
localhost/testsite, then you need to set the RewriteBase to /testsite. There can also be a problem with Options +FollowSymlinks line.
I'm sorry but I cannot help you more. If neither of this helps, you should probably discuss the .htaccess and server configuration with your web host, or if you are developing locally, you could try searching google for answers on server and .htaccess configuration.
Best regards,
ARTIO Support Team