Most IMAP problems come from the password or the server settings, and Newton's error tells you which. Sign-in failed points to the password. Could not reach the server points to the server settings.
Try these, in order
Use an app password. iCloud, Yahoo, AOL and Fastmail don't accept your normal password. Create an app password with your provider and paste it into the password field.
Pick your provider. Choose iCloud Mail, Yahoo Mail, Fastmail, Zoho Mail, AOL Mail or GMX instead of Custom, and Newton fills in the server settings for you.
Check the username. It's usually your full email address. Change it only if your provider uses a different one: under Server settings on desktop, or in Username (if different from email) on your phone.
Check the server settings. Open Server settings and compare them with your provider's help page:
Incoming (IMAP): port 993 with SSL/TLS, or 143 with STARTTLS.
Outgoing (SMTP): port 465 with SSL/TLS, or 587 with STARTTLS.
Turn on IMAP with your provider. Some providers, such as Zoho, need IMAP access switched on in their own settings first.
Use the right option for Gmail and Outlook. For Gmail, Google Workspace, Outlook.com and Microsoft 365, choose Google, Outlook or Microsoft 365 instead of IMAP.
On desktop, click Test connection before Connect. Connected — … folders found means your incoming settings work.
Good to know
Test connection checks your incoming server only. A wrong outgoing setting shows up the first time you send.
You can add IMAP accounts in the desktop and phone apps, but not at account.newtonhq.com.
Newton doesn't support POP.
Newton marks the None security option "not recommended". Use it only if your provider tells you to.