Relay access denied from Gmail for Zoho setup domain

My domain is setup under zoho with correct DNS.

Sometimes, when users email, they receive this email in Gmail/Yahoo:

Gmail Error Message received by a user

DKIM/SPF and everything else is setup as Zoho wants. I would love some help. Thank you!