Shopify App Gets Caught in Infinite 'Enable Cookies' loop in Safari

We’ve upgraded to v3.1.61 and now in the initial authentication process we get the following error:

Request origin could not be verified

It happens in all browsers.

Only in the second attempt to authenticate, it works well.

Any ideas?