I tracked it down, thanks to some info in this article by David Hoerster. The problem is that the default password hashing algorithm on Azure is different from the .NET 4.0 defaults. It is set to SHA1 on Azure, and HMACSHA256 is the new standard setting on 4.0.
This can be fixed by specifying the hash type explicitly in web.config. If you decide to use a method like HMACSHA256, make sure you also specify a machine key - otherwise you will run into similar problems as the autogenerated machine key will differ from server to server.
The configuration element you need to change is <machinekey> under <system.web>:
You can use this machine key generator to generate random keys in the proper format.