JoomSEF's 404 page is realized as static content page in Joomla!. Just make sure it exists and is available for public users. Then it should work fine.
If you meet both these conditions and it still does not work, please post some example here that we can check closer.
