Very strange. Emails mostly don't sent right away when I click Send... that's when I get the error message. But when I check my phone 2 hours later, the email was sent (at some point in the last 2 hours). So I guess they're going, they're just really really slow? A slow connection with the server that causes it to timeout sometimes but work other times? I would think if AVG was the problem, it would block it 100% of the time?
That article is for a PC based AVG Email Scanner. I am using the Android 5.0 operating system on my phablet.
The behavior you describe would mean that there is a problem with the initial connection to the SMTP (outgoing mail) server, but then, on a subsequent connection it works. It is very much possible that AVG is at fault here. If before the installation of AVG, Aquamail wasn't behaving like this, that gives even more weight to that guess.
If it is known to create problems on one OS, it is logical to assume it may create similar problems on a different OS. So, I would recommend disabling AVG and checking if the behavior changes. I cannot tell you with the 100% confidence that it is AVG's fault, but it is very likely, and it is easy to test (assuming that you are looking for a solution) as a first step.