No meu caso, recebi essa exceção mesmo quando todos os valores de parâmetro foram fornecidos corretamente, mas o tipo de comando não foi especificado:
cmd.CommandType = System.Data.CommandType.StoredProcedure;
Obviamente, este não é o caso na pergunta acima, mas a descrição da exceção não é muito clara neste caso, então decidi especificar isso.
