I just came across this issue again on a clean format many months later, so I began to suspect it's some software I'm installing that's doing it, and I have found one cause of this error. Since it has been so long I assume you've already found your own workaround, so this is mostly to help anyone finding this page when searching for the error themselves.
I am using an application called DisplayFusion, which amongst other things extends your taskbar to other monitors. To replicate the Visio problem you described above, I just need to install the software, and I have the problem. However, by unchecking "Enable global application hooks" in DisplayFusion Settings > Troubleshooting, the problem immediately goes away and I can once again create styles in Visio. Toggling this on/off immediately makes the problem come back or go away, so it looks like it is caused by some in-memory interference rather than a file or registry setting, which was my first suspicion.
While this software is certainly not the only cause of the error, I hope this information helps someone track down the cause of the problem on their own machine.
Some search strings that may help someone find this post:
A name is required. Enter a name.
Visio Styles
Cannot create a new style
Can't create a new style