So, I had users getting strange errors trying to connect via ActiveSync to ZCS NE 7.1.3 after installing zimbra-proxy. Google found nobody that was getting these errors, so I'm mostly posting this so it'll show up in searches for any future people who run into this error.
The users who were unable to log in would have errors like this show up in mailbox.log:
2011-12-31 11:43:28,642 INFO [btpool0-76://mailbox1.hostname.com/service/extension/nginx-lookup]  nginx - user not found:firstname.lastname@example.org@our.public.service.hostn ame.com
Note the two @ signs in there. Turns out several of our users had put the domain name of the server into their "Domain" field in the ActiveSync setup. When talking to Zimbra's mailbox server directly it apparently takes this. The proxy authentication within nginx does not. In order for authentication via nginx to work, the users needed to leave the "Domain" field blank in their ActiveSync config.