Hello,

if you see 404 error, then most likely you
1) do not have your .htaccess file created
or
2) the RewriteBase within is not set correctly
or
3) mod_rewrite is not activated at your server

Please, see details in:
JoomSEF FAQ: "404 Page not found" error after clicking any link

If the problem is just with some links, not all, then double check the URL is stored in JoomSEF URL Manager and that the non-SEF version is really correct. If there exists more versions of the non-SEF URL for a single SEF URL, click the "activate" for the one that you are sure it is correct.