There are plenty of secure email applications, but Petraeus couldn't use any of them.
In other words, Petraeus could not be seen using those applications. Official secure email goes through official secure channels. Personal email went to through gmail / yahoo / etc.
If someone had found out Petraeus was using a different email app (and I'm sure they would have), it would have immediately raised suspicions as to why the Director of the CIA was using a secure email app that wasn't the gov's official secure email app.
I think the safest thing for Petraeus would have been to only send short coded messages via gmail (e.g. "talk at 10 pm" but replace that text with code words) and then to conduct most of the communication infrequently and in person.
This is exactly it. For Petraeus, even a secure, encrypted email solution wouldn't have solved the problem. Because he would have been seen to have been using it. Even something that encrypted the emails in-transit would have been a problem, because then the FBI still would have discovered a large number of emails b/w him and the mistress. Even if she was a biographer of his, the volume of email (and timestamps) would probably have been a good clue that there was something else going on.