A recent Microsoft Security Update (KB3002657) for Windows Server 2003 will cause Windows Authentication problems when connecting to SQL Server (in my case SQL Server 2008 R2). When trying to connect to a Geodatabase with Windows Authentication an error will result saying Failed to connect to database...The login is from an untrusted domain and cannot be used with Windows authentication. No extended error.
You may ask, "why are you on Windows Server 2003?" Our data is not on Win Server 2003, our domain controllers are running 2003 and this is what was causing the problem.
If you're experiencing this issue, remove the update and it should fix the problem.