MSN Explorer: MSN stops responding during sign in and a flying butterfly appears

If you can't sign in to MSN, but you receive no error message and a flying butterfly appears on the screen:

MSN Explorer: MSN crashes, stops responding, or experiences internal errors
MSN Explorer: You were not signed in because the server could not verify your membership status