Same issue. Specifically, no user is able to access other user's shared contacts, using the Open Shared Contacts button. The user receives a message saying, "You do not have permissions to view this contacts folder. Do you want to ask <user display name> to share their contacts folder with you?"
I confirmed the user has up to Owner access on the shared contacts folder I am trying to get access to. I have reproduced the problem with several user accounts and contacts list and have the same problem.
Note: The problem only impacts shared contacts folders. Shared calendars can be shared and added without an issue.
Workaround: As hinted by the answers above, I have successfully granted access to shared Contacts by granting foldervisible permissions to the top of the information store, e.g. set-mailboxfolderpermissions targetuser@demoxyz.com -user sourceuser@demoxyz.com -accessrights foldervisible
As long as the user also had permissions set on the shared Contacts folder in addition to the Top of Information Store permissions, then you can add the target mailbox in File > Account Settings > Account Settings > Double click the email address > More Settings > Advanced Settings > Add. Once added, of course, this maps the user's mailbox to the folder list, though without granting access (it cannot be expanded). You will then see the shared contacts folder appear in the Contacts (People [groan]) list.
I am piling on with a ticket to Microsoft. I cannot tell how many are impacted, and existing shared Contacts access appears to be unaffected. In my testing, if you can successfully access an existing shared Contacts folder and delete it, you are unable to add again despite having access.