Parece que a nova versão da Command Line Tool baixada da App Store está corrompida. Eu tive que baixar o mesmo da mesma versão da página Apple Developers Downloads e instalá-lo manualmente.
Em seguida, abra a App Store, vá para a guia Atualizações, deixe-a atualizar a lista de aplicativos um pouco. E a ferramenta de linha de comando desapareceu porque já está instalada. Agora posso continuar com minha atualização do OS X:)