Pre-authentication fail Event ID 672, 673, 675 everywhere

[1LUV1T]

Hello all, after much browsing and researching I am stumped as to why my Domain Users are failing Pre-authentication (675)every time and also why Authentication Ticket Requests are failing (672) with a blank message (673). I am in an Active Directory/Windows 2003 domain environment.

The strange part is, this just began a few days ago, and *some* of the Pre-authentication errors such as Event ID 672 show Username as the Outlook email address (we're not running Exchange, just Outlook RPC/Http).

Example of EventID 672:
Event Type: Failure Audit
Event Source: Security
Event Category: Account Logon
Event ID: 672
Date: 9/5/2008
Time: 1:51:00 PM
User: NT AUTHORITY\SYSTEM
Computer: MYDOMAINCONTROLLER
Description:
Authentication Ticket Request:
User Name: john.smith@email.com
Supplied Realm Name: MYDOMAIN.COM
User ID: -
Service Name: krbtgt/MYDOMAIN.COM
Service ID: -
Ticket Options: 0x40810010
Result Code: 0x6
Ticket Encryption Type: -
Pre-Authentication Type: -
Client Address: XXX.XXX.1.101
Certificate Issuer Name:
Certificate Serial Number:
Certificate Thumbprint:

Example of EventID 675:
Event Type: Failure Audit
Event Source: Security
Event Category: Account Logon
Event ID: 675
Date: 9/5/2008
Time: 2:07:58 PM
User: NT AUTHORITY\SYSTEM
Computer: MYDOMAINCONTROLLER
Description:
Pre-authentication failed:
User Name: user01
User ID: MYDOMAIN\user01
Service Name: krbtgt/MYDOMAIN
Pre-Authentication Type: 0x2
Failure Code: 0x18
Client Address: xxx.xxx.1.136

I read a good explanation of Kerberos Authentication in relation to my problem is found her;

http://www.windowsecurity.com/articles/Kerberos-Authentication-Events.html.

However, it describes my errors as a result of bad user login password, however, that is not the case as all users log in just fine.