Hello Andy,
are you sure your JoomSEF is working fine otherwise?
If you are still seeing index.php and that is not configured in JoomSEF as the default index filename, make sure the URLs are not hardcoded in your template or elsewhere in code.
Also, if you are getting non-JoomSEF 404 page although it is configured, it may be processed differently by your http server - e.g. if the URL matches existing directory name or filename.
Maybe you could be more specific about those.
If you are paying customer, you can put your question in paying users thread next time.