This was a new cPanel server and I was setting up the first account for email but tests via the webmail client were not being sent. The error was similar to the title of the post with a ‘Try again later’ message.
So I went trawling through the account settings and came up with nothing. So I read somewhere the the /etc/localdomains may be the issue, so I checked that file and the appropriate domain was there in all its glory so that was not the issue.
More Google searching and I wind up at the appropriate cpanel forum with a post that appeared relevant.
The post that caught my eye was the one that suggested to run script to fix /etc/localdomains
You can run /scripts/mailperm and it will add all domains to the /etc/localdomains
So I ran this and despite the being no apparent change to /etc/localdomains the email is now working. My guess without looking at the mailperm script, is that it does something more than just set the localdomains list. No time to investigate further and its working.