Descobri isso. O arquivo de script foi criado usando o PowerShell ISE e aparentemente você não é possível assinar scripts criados no PowerShell ISE ou, mais precisamente, você não pode assinar arquivos codificados em Big Endian Unicode, que é o padrão para o ISE. Há uma solução alternativa para alterar a codificação padrão, conforme documentado no link.
Originalmente adicionado à pergunta por Chad Miller . Relocou sua atualização para uma resposta, então essa pergunta não aparece mais como não respondida.