Same for me with a Zimbra account.
If using IMAP/SMTP configuration, everything works.
If using third-party mail configuration for AES (instead of native one), it works as I have tested it with "Moxier Mais (Exchange) - Trial"
If using other phones (Samsung Galaxy S with CyanogenMod, or iPhone 4 with iOS7), Exchange works as a charm...
The phone security policy which can be required by AES have been turn down for my Zimbra account by administrator...
Conclusion: there is something realy wrong with the native AES configuration in the GS4 (Android 4.3)... Official Android 4.4 should come by the end of January 2014 for this device, lets hope it will correct that!
Partial solution can be found here: http://forum.xda-developers.com/show....php?t=2571979