Unfortunately, a lot of these issues seem to be caused by small differences in pre-existing configuration or packages. I did attempt to debug one of these issues before (coincidentally it's the one you're having now), and was unable to reproduce the issue. I just tried the same commands you are using on a clean instance (Amazon Linux AMI 2015.09.1 x86_64 HVM GP2) and they worked fine.
What's weird to me is that the client doesn't seem to be reinstalling dependencies when you run letsencrypt-auto, which it should do after you deleted /root/.local/share/letsencrypt. Specifically, you should see something like
Bootstrapping dependencies for Amazon Linux...
followed by some yum output. Just tried this myself, and that's what I got.
Here's the thread I was referring to - the OP did find a fix eventually, maybe it'll be of use to you: