Wherever the problem lies, the issue is unfortunately probably up to Square Enix to resolve. We're unable to submit a support request for the game via Steam, as following their support wizard to try just results in a page saying that they can't help with third party games. If the issue is with Steam Authentication, there's likely no way for us as users to let Steam know what's going on.
The onus, therefore, is on us to let Square Enix know what's going on (we're doing what we can right now, by making these posts in these forum threads), and then Square Enix to liaise with Steam to resolve whatever the underlying issue is. Since it's a Sunday, I'm not sure that there's going to be anyone from Technical Support in either company available to hit their respective servers with a hammer. So, unless this issue is one that simply self-resolves after a period of time, we probably won't be getting a solution today.
However, I would encourage people to make this issue known via contacting Square Enix support directly. Maybe if enough people bring it up, they can make it a more prominent issue to address.