I feel rather silly having wasted so much time on this. The issue was I was using an ATD image as I wanted to test without Google Services. Should have just been using the "Default" one.