Hello,
well, if neither the standard Joomla! SEO works, then it is either problem with your .htaccess file or your webserver mod_rewrite in general.
1. make sure your .htaccess has uncommented the lines as needed for SEF and JoomSEF (check the documentation if your are not sure; also there is help in the .htaccess self)
2. make sure the mod_rewrite is installed in the web server and that it is enabled for your site (if you host your site, contact your hosting provider to learn this)
It is good to make the standard Joomla! SEF work first. After you are done with that, turn JoomSEF on. If you have problems, you may contact the ARTIO support. We may be able to help you make SEO running for a small fee.
Best regards,
Honza