Blackberry and iPhones not synching with Exchange 2003 (Device Password)

Yesterday I received a request to set up a new iPhone user in an organisation.
All the account details were on the phone already and all accurate, it just wouldnt validate and connect.
Now I wasnt aware that there were already 2 iPhone users in the organisation working perfectly well.
I thought it was a setting on the Exchange server that needed to be changed. After a lot of googling I attempted to get the user set up.

On the Mobile Devices Properties in Exchange 2003, I ticked the box for Enforce Device Password in my haste.

I have received a call today that none of the mobile device users can connect to the Exchange.

I went to the offices and there was a Blackberry there for me to look at.
The emails stopped synching at basically the exact same time I was changing settings yesterday.

There was also 2 event logs on the server:

Failed events:
2 matching event log records found in the 'Application' event log.
First matching event found: Source = crypt32, Event = 11, Date = 08/12/2010, Time = 02:33:28 PM, Type = Error, Event Description: Failed extract of third-party root list from auto update
cab at:

with error:
A required certificate is not within its validity period when verifying against the current system clock or the timestamp in the signed file.


AND


Failed events:
1 matching event log record found in the 'System' event log.
First matching event found: Source = Schannel, Event = 36871, Date = 08/12/2010, Time = 02:53:58 PM, Type = Error, Event Description: A fatal error occurred while creating an SSL server
credential.


I was also adding certificates yesterday to the properties of the mobile devices (or making sure the certificates were correctly installed)

The rest of the email, including OWA is working fine now so I think it's just the mobile devices I need to resolve.

I thought it might be to do with the certificates or SSL settings or SSL ports (for mobile devices the SSL is set to port 993 rather than 443 - is this regular?)

The Blackberry users are getting an email about updating their password:

donotreply@blackberry.com (Subject - Action Required-update password), emails will not longer be received to the device until the update is complete

When I go to the Vodafone mobile email website to do this, it says the account is invalid.

The iPhone users get an error saying no more emails will be delivered until a passcode is entered.

Now is it just a matter of deleting recreating the accounts on these devices?
And how do I go about doing that on them?

Please help someone or I may be finding myself without a job!

Thanks in advance.