iMessage has been down a few times, even recently but I personally don't think that they are linked.
I remember having this issue before, exchange emails (usually for work) require that both accounts at work and phone passwords match. Make sure that the password is the same for both. That, or somewhere in the process of syncing the phone, phone synced a previous account?
If anything, try removing the exchange account and adding it back in the queue.