I installed MSDE SP3 as per MS's directions. However, running Enterprise Manager and trying to register the SQL Server instance into a group (this is on the same box that MSDE was installed, BTW) resulted in the old "Server does not exist or access denied" error. This occured whether I used SQL or NT authentication. After the 5th re-install - luckily, I had taken a snap-shot of the machine beforehand, so was able to quickly return to its original state - I figured something was wrong.
The MSKB didn't help, and none of the solutions I was suggested to try worked. What DID work was running SVRNETCN (Start/Run/SVRNETCN). This popped up a basic dialog which immediately told me that SQL wasn't "connected" with any protocol. I clicked TCP/IP over into the right-hand box, clicked Apply and viola! The server registered.
It appears that SP3 installs with no protocol defined. This is in contrast to previous flavours: I'd never encountered SVRNETCN before, as previous installations simply worked.