Ah so it's not a profile thing then. Just perhaps a coincidence, but as you say it's bloody bonkers and driving me mad!
i had the same error message (some account services not available until i log in again).
in my case it related to (was a warning about) Messages not using the same iCloud account.
but a simple log in was not able to ever fix it.
i think for me it was related to / caused by this unholy combination of events:
(1) my having switched a SIM card from one carrier to a different carrier
(2) the new SIM card's mobile number not resolving (in Messages/Facetime) to be able to seemingly used (reachable)
(3) the 2nd SIM does need a Profile in order to get data (its a SIM from an MVNO that needs a profile in order to access data using a different carrier's network) the Profile was installed but maybe not being accessed somehow.
(4) upgrading iOS to the next point level upgrade (yes!)
even nuking the whole thing (total reset of all settings, network, data) didn't fix the problem.
but as someone else has mentioned, i noticed that there was also a hint of a different / related (?) problem:
my Keychain would not allow syncing.
when i tried to switch on Keychain sync in the iCloud settings it just kept rejecting it.
so i began to think cross platform about what was happening on my mac.
i turned off iCloud on my mac (yes, a drastic attempt to fix this as it involves downloading all my music again) and then did another reset on my iPhone with no iCloud turned on on my mac.
so there were no other devices signed in to my iCloud account.
so unless its apple's problem, everything should work well on a single, iOS device accessing my iCloud account.
and it did work !
then turned on iCloud on my mac.
i think the Messages settings on mac and iPhone were not able to be resolved and that led to the problem.
the problem seems to have been that my SIM profile would allow messages that were addressed only to the phone number (even iMessages as long as it was to the mobile number) but the iOS system's Messages was unable to associated that mobile number with being able to receive messages - or something like that...
weirdly, after all this, my Message threads were all jumbled ( mean really really jumbled) but i just kept hitting that sync button on mac Messages and about an hour later it all sorted itself out.
its all good now, however. and iOS and macOS Catalina are working well together at last.