No,
ReDJ and sh404SEF can work together without problems.
Could you, please, check if the error 404 is returned by Apache or Joomla?
If is Apache that send the error page, this mean Joomla doesn't receive your call (and ReDJ can't do the work).
If you get the Joomla error page, it means that ReDJ doesn't find any matching URL. In this case, try to use redirect mode in your plugin settings (this is because you are using sf404SEF). If the problem persists, send me a dump of ReDJ table.
Regards,
Luigi