I own an iPhone SE running iOS 12.3.1.
I clicked on a webpage link to for Google Translate and got the message that about inability to log in to the App store. I thought this might be due to the fact that I never log in to iCloud. In the course of troubleshooting, I changed my Apple ID password, got forced to change my Apple ID from MyOldAppleID to AnEmailAddress@somewhere.com, logged out of iCloud from attempts made today, powered down, powered up, logged back in, got forced to use 2-factor authentication, found that there were two GUI navigation pathways to get to the App Store, and tried them both:
Settings -> Top option -> iTunes & AppStore
Settings -> iTunes & AppStore -> Sign In
In the 1st case, the "iTunes & AppStore" field stays "off".
In the 2nd case, the "Sign In" link remains blue, and the area to the right remains blank (I assume that it is unblank if I'm logged in).
In both cases, clicking on the App Store "Retry" button simply re-displays "Connot Connect to App Store"
I am in a foreign continent across the pond, so have limited options for getting real time forms of assistance. I am also on the road (well, in a diner), so can't do lengthy power, consuming changes. Not sure if there is an Apple store in Berlin, but not sure that I want to waste the valuable and short amount of time here running around the city fixing the iPhone problem, though frankly, I've already done to a significant degree. However, I may have to suck up the inability to install a translation app.
The only thing that I didn't do was choose to merge my navigator options and contacts with iCloud during the login. It doesn't seem logical for that to be necessary to access the App Store. I chose to switch to Apple to get away from being at the mercy of the juggernauts in privacy relinquishing ways. If uploading contacts is needed to in order to access the App Store, then in essence, Apple is holding the phone functionality hostage for not just my own personal data, but also data of everyone I know, who never agreed to having their info in the cloud. I hope this is not the source of the problem, but it's the only remaining wild card that I can think of right now.
Best Answer
It looks like it was just a matter of time before Apple sync'd its user authentication information across services. The new iTunes login seems to work now, 1.5 days later.
It sure would have been nice to be have been notified of this when forced to change the ID, and it would have taken zero effort in the course of developing the change process.