Do you have any other wisdom regarding mysterious reasons for fast or slow booting? EC2's boot process is deeply opaque, and any insight at all is better than nothing.
Nothing comes to mind, but if you want to drop me an email I can walk you through some benchmarking.