It seems you’ve left out one key detail to this puzzle….what service is it that is failing upon reboot? This may tell a lot in regards to where the problem lies.
As for SP1 for Windows Server 2003, this SP should not have any affect on replication with non-SP1 DC’s nor should it not play nice with Novell. We don’t use any Netware servers in our environment, but we do have one 2003 DC running on old hardware (lack of disk space) which currently is not running SP1 and replecates fine with two other DC’s w/ SP1 running on new hardware.
Please post the failing service and possibly it will generate some better response.