Apple Messages Not Working At All After Update
Turns out that the culprit was an iPad. I've never used it for Messages, so it never occurred to me to disable iMessage on it.

You have to disable it on all devices to get it to properly reset, even if you've never opened the app on one.

Thanks for the tips.