Cannot login SQL Server after changing machine name

After installing and setting up new machines in a domain, we decided to rename one of them which had a SQL Server instance installed. So I changed the hostname, everything went fine regarding the domain but now, the server is logging a approximatively 2 SQL Server errors every 5 minutes and I cannot connect to the instance localy or from anywhere within the domain.

Here is the error from the event log:

SSPI handshake failed with error code 0x8009030c, state 14 while establishing a connection with integrated security; the connection has been closed. Reason: AcceptSecurityContext failed. The Windows error code indicates the cause of failure. The logon attempt failed [CLIENT: x.x.x.x]

Concerning the instance, everything is started and restarted without any extra error.

I would say all your logins were of the form of 'computername\username' and because the computername is now different the logins don't not work anymore. If you don't have SQL-Authentication of the 'sa' password, you need to start SQL-Server in single-user mode in which any local administrator has access and you can fix your broken logins.