There's a possibility that this issue might be related to HVM. All of our AWS systems are on older, non-hvm instance types, and none have been rebooted, and there are no maintenance events listed. Friends who are using newer instances (which are all hvm) are reporting the reboot issues.
Anecdata, but a possible explanation.