I think I may have cracked the case...
I think it may have had something to do with contact groups - the "Groups" menu item that was in contacts, when tapped, would show a message of no affiliated application, which, is expected when using a white list option.
Added com.samsung.android.contacts to the white listed applications (I had com.samsung.android.task.contacts white-listed)
Then I simply going to Settings > Apps > Contacts > Storage and click on Clear Data
Our contacts are synchronised from a shared Google account so simply re-downloaded them.
Voila!
We now have contacts back, along with "Groups" menu item working
Thanks for your insights.
Hopefully, this will help someone someday!