I solved this by going to the App Store and installing Xcode.
It was a pretty large 11GB install, so this is probably overkill. But, as a last resort, it seems to have solve my issues. In the middle of the installation (well around 10GB), Mac OS told me there was an update to Command Line Tools for Xcode. Performing this installation won't fix anything until Xcode is fully installed.
Once the install is done, it should start working (after you accept the license agreement).