Has Google just stopped supporting Amazon Fire Phone?
This seems to be due to a bug in the current version of Google Play Services, and it's not just limited to Fire Phones. There's a discussion about it over at XDA Developers, which I'd recommend keeping an eye on. 

For now there doesn't seem to be a good solution yet other than uninstalling Google Play Services and reloading an older version - and even then rebooting the phone will automatically update Google Play Services to the broken version. I've seen some commenters say that uninstalling the Play Store will keep Play Services from updating, but I haven't tried that yet.