The reason this fails is that the server sending the response has keep-alive turned off. Notice the "Connection: close" header that was sent? This tells cURL to stop what it's doing and not attempt to follow the redirect, even though it got the "location" header. In short, cURL is perhaps a bit too polite, by respectfully honoring the server's request to close the connection, rather than requesting the location specified in the header anyways.
If anyone has a solution to this problem, I'd love to hear it.