Possible reasons I have seen:

1. Lost connection to Active Directory from WFE and/or SQL Server - by far the
most common reason I see. Actually, it's been when DCs/GCs are behind a firewall
and/or IP address changes (oh, one customer was because they used AD clustering
and couldn't hold the virtual IP steady).
2. I/O overload
3. Incorrect aliasing setup
4. Some other authN anomaly or incorrect setup - maybe some others on here can
toss in their ideas?

I would try capturing data with wireshark if the pattern is predictable.

I believe we did patches, updates and reboots of a lot of our systems
that night. I will have to find out if AD was down at any time.

I know you say that everything has been the same, but is there any chance
that SSRS was recently installed?

Is the value of 'databasename' not the same as 'SharePoint_Sites'? Also,
what sort of DB is this?

No SSRS recently installed and yes the 'databasename' is the same
as 'SharePoint_Sites'.