Well, I've got iOS 7.0.4 on 2 iPhone 5s, an iPhone 5c, and iPhone 4s and an iPhone 4, and 2 iPad minis, and all are receiving mail without having to go through what you are experiencing, so I wouldn't say it is the iOS. Have you done any troubleshooting of the phone, other than just deleting the mail account? I would say start with a restore from backup. If that does not fix it, then a restore as new. That will delete everything off the phone and put in a new version of iOS and then you can add things back.
One last thing I was thinking as I sent this. Is this a POP account? If it is POP and you are accessing from multiple devices, are you accessing anything at the same time. In other words, do they have fetch settings on them? It is possible that more than one device tries to access the account at the same time, and the server is locked and could produce a similar error message on one device if another is accessing the server.