Problem Scheduling in Outlook (2007)

I have two users who try to schedule appointments in Microsoft Outlook when they try to save the appoint they receive an error message stating: "The connection to the Microsoft Exchange is unavailable. Outlook must be online or connected to complete this action."

Outlook appears online, as well as connected to Microsoft Exchange server. Tried repairing Outlook. No such luck thus far.

Any help would be greatly, greatly appreciated as i am on a timed schedule to get this problem resolved.