You may want to verify that the Messaging Gateway is set to the correct time. This can happen if the Kerberos tokens are not within 5 minutes of each other.
The easiest way to determine the current time is to click the Status section and look at the top where it states the period for the report, it'll say something like:
Thursday, Jul 12, 2012 12:00 PM to Friday, Jul 13, 2012 12:24 PM PDT
That end time is what the Messaging Gateway thinks teh current time is. If it is not correct, you should go into the Administration -> Configuration -> Control Center -> DNS/Time tab and set the time manually.