Fixed! Kind of.
You will need to do this every time you reboot.
Thanks for the free "upgrade", Microsoft.
Here are the steps:
1. Press F8 at the blinking cursor between your bios flash screen or POST complete and the start of Windows loading (you probably only have a second, so be fast). Sometimes this doesn't work the first try, so reboot and keep trying if nothing happens.
2. Boot into safe mode with networking. (I don't know for sure that networking is required, but that's what I used, so I'm playing it safe).
3. Press "Windows Key + R", type netplwiz, and click "OK".
4. Make sure the box labeled "Users must enter a user name and password to use this computer" IS checked. Click "Apply" and then "OK" (old superstition: I always do both).
5. Reboot, and enter your credentials.
6. If this doesn't work, then see the answer marked below.
Conclusion: Something is wrong with the way that Windows 8.1 stores or loads user credentials. I use my Microsoft login for Windows 8.1, but since I haven't tried to reproduce this with a normal login, I don't know if it's unique to that. I *did* change my password online just before upgrading to 8.1, and I *have* updated my password locally. I suspect that 8.1 is still trying to use the old password from before it was changed, just before the upgrade. I hope that this helps Microsoft to fix this problem.