Unsure if this is related, but a few weeks back AWS paravirtualized instances were experiencing extreme clock skew and suffering frequent restarts. Our clocks were skewing about 8 seconds per hour, and the instances were getting swapped out at least once per day, sometimes more.

Switching to a HVM instance type resolved the problems.