Well, I have to record this here as it was a strange one. I found my fix here: https://www.megaleecher.net/Fix_Windows_Cannot_Access_Error. In my case, a disk recovery program, Diskinternals EFS Recovery, had replaced the "ProviderOrder" entry under registry key HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\NetworkProvider\Order with the value "cbfsconnect2017-0". Once I put back the Windows default, "RDPNP,LanmanWorkstation,webclient" things immediately started working again (without a reboot unlike what that post says, but no guarantees - you may have to reboot).
The really strange thing was that I could do a "Start, Run" and connect to any folder that was at least two folders deep (It would auto complete folder names as I typed \\ServerName\etc.). E.g. I could connect to \\ServerName\ShareName\Subfolder but not \\ServerName or \\ServerName\ShareName) and when I viewed the address bar in Windows File Explorer, it looked like "> Network > ServerName > \\ServerName\ShareName > FolderName" (yes, with the slashes) instead of "> Network > ServerName > ShareName > FolderName"
When I clicked to the right of the address (to copy it out) it showed as "\\ServerName\ShareName\Subfolder". Once I got to the subfolder I could then navigate up a folder to the root share (either with Alt+Up Arrow or clicking "\\ServerName\ShareName" in the address bar). But I still couldn't get all the way up to see a list of the server shares without receiving an error.
Other Google search terms for this are "The network is not present or not started." (it switched between that error and "the specified network provider name is invalid") and "System error 1222 has occurred. The network is not present or not started." (which I received when running "net use" from a command prompt).