Android: Unfortunately Google Play services has stopped

For some time I was getting "Unfortunately Google Play Services has stopped" on my Nexus 5 Android. What fixed it for me was a factory reset, followed by a strict app pruning session!