I'm trying to add a Recovery Contact, but no matter who I put in, I get a window saying "Unable to add Recovery Contact. Try again later ". What do I do from here?

Maybe the recovery contact that you are trying to add does not meet one or more of the requirements given below

Requirements to be a recovery contact

• Your device must be running iOS 15, iPadOS 15 or macOS Monterey or later.
• You must be over the age of 13.
• You need two-factor authentication turned on for your Apple ID.
• You need a passcode set up on your device.

I unsuccessfully attempted to add Recovery Contact who met all criteria you listed. I suggest also that users ensure Contact person has selected iPhone Settings for iMessage service "ON"

If iCloud is offline, iMessage & other apps reliant on it also lose functionality.

side note: To further complicate my situation, recovery contact apparently resides where connectivity so inconsistent, texts are rarely via iMessage service.