"Prelogin failure" when attempting to run stored procedure across linked server
I've seen it happen twice after SQL Server service packs were applied - service packs that took a really long time (hours) to finish the upgrade, or broke as they were trying to apply changes to the system databases.

The fact that you mentioned there was a scheduled restart clues me in, too - that means someone had probably staged updates to happen on restart, and they did - but then they caused an outage.

As a result of this, I'm never a big fan of automatically applying updates (Windows or SQL) on SQL Servers.