Following up I have had a reply from Meta Support
“Upon checking, you are not required to complete your verification yet. Rest assured that your shop is already visible as well as your products, as it’s already showing as approved”
Just checked and it’s letting me tag my products again, although Shopify still not displaying as connected in the products tab, the error message isn’t there anymore…