Yup, EC2 instances should be issuing a gratuitous arp on startup. I've seen the same thing on subnets with a lot of DHCP churn due to constantly rebooting embedded devices.

Pretty much textbook symptoms of arp-caching.