I have an original "NeXTstep Concepts" manual with the NX prefix. I can't remember where I heard the "NeXT and Sun" explanation for the first time, but a Google search shows that the prefix change could've actually occurred before the collaboration with Sun. It could stand for NeXT Software, as it's closer to the transition to a software company.
The "NS" prefix was introduced with OpenStep in 1994[1]. OpenStep was a collaboration between NeXT and Sun[2]. So the S in "NS" referring to Sun is certainly plausible!
A person that was involved with the project claims the prefix predates Sun's involvement [1].
> Totally wrong. The NS prefix predated Sun signing on to implement the OpenStep spec by quite a bit. It was either NS for “NeXTStep” or “New System”. None of us can remember which, though, but definitely not NeXT-Sun.