I may have stumbled on the solution to the "problem establishing player service" notification which had annoyed me for almost a year. I now use my kindle app on a Galaxy Tablet but had used the Kindle app on my Galaxy III phone before that. Both devices are registered to the same Amazon Kindle account but I hadn't access the kindle app on the Galaxy III phone for more than a year. All I did was to open the Kindle app on my Galaxy III phone which automatically sync the app and that annoying notification stop appearing in the app on my current device. It's been 24 hours so I am quite certain the problem is solved for me. For those who do not have access to their older devices still registered to their account can perhaps try de-registering that device?
"Problem establishing player service" came back in the kindle app on my new device after 5 days. I open the kindle app in my old device again to sync content, close kindle app in my new device and re-open... tadaa no more "Problem establishing player service" message.