Clearing all data from google services and google play games works for me but only once. Any subsequent runs of the game present the same problem (Showing logged in to google play but in settigs PFID says not logged in).
Unfortunately this does not work for me on a S6 Edge+ running 6.0.1. Do you need a logcat perhaps? Or anything else from the device (dmesg etc) that can help debugging this?