Error Creating New Contact Through OWA

We have a Public Folder containing a large list of contacts (about 4900) and a couple of weeks ago a service used to keep it synced with another contacts database began experiencing errors.  The service uses OWA to log in to the sync user account and create new contacts in the public folder but it is now unable to do so.  I have tested the user account's ability to create a new contact via the full version of Outlook and it is able to create new entries (it has Owner permissions).  However, when using OWA on IE7 it receives the error "An internal server error occurred."  I have also set up my user account with Owner permissions on the public folder and while I can create new contact items via Outlook I cannot do so via OWA and I receive the same error.  The only thing that was changed the day these errors started occurring were two other user accounts had their passwords changed and were removed from distribution lists but the sync user was not changed and no accounts were deleted/deactivated.  About a week later the server was rebooted but the error has continued to occur following the reboot.

The issue does not appear to be permissions related since the sync user and myself can create new contact items via Outlook but just not via OWA.  What's the next thing to check?