google play services is not supported by kindle fire
Use this version. My Fire was working perfectly until this week so the solution seems easy: to move to GPServices previous version.

Google Play services 7.0.99 (1809214-038)

Good luck.