You don't mention the OS you're running but this is reminiscent of Ubuntu #708920.
https://bugs.launchpad.net/ubuntu/+source/linux-ec2/+bug/708920 This always occurred for us on the Nehalem architectures, you might try and boot multiple instances until you get an older Xeon (these days usually takes a dozen or so instances), see if you can repro on a different architecture.
