Turns out that it was cause by Spring Security. We are using Spring Security 3.1x, and by default it stores the authenticated credentials in the user's session. And to counter session fixation attacks, it automatically copies the contents of the user's session to a new session id and invalidates the old session.
The fix was to add the following to the http element in the security configuration, since we don't need to use the session in our application:
create-session="stateless"
Hopefully this helps someone else down the line.