Hello,
current version of JoomSEF works fine both with PHP5 and PHP4.
If you are getting 404 erros, this is mostly because error in .htaccess file. Either 3rd party section is not uncommented, or RewriteBase is wrong. Please, check the JoomSEF FAQs.
If you are sure, both of those are okay, you may purchase the paid support and our admins can configure JoomSEF for your.
Best regards,
ARTIO Support Team