I was also struggling to get an old HTC Flyer tablet, running a Honey Comb ROM (LeeDroid v4.3.0 from XDA), to connect to Google Play after a factory reset. I tried many many things, but this was what resolved the issue:
1) Downloaded and installed the latest version of both Google Play Services...