An old message, but I am having the exact same problem.
I have completed all updates and play store updates, but get the error message.
I did have a work round where a QR code would work, but now it is unable to connect to server regardless.
Samsung Galaxy A10