I've been banging my head on this until I realised it's actually alarmingly easy.
$web = Get-SPWeb <site url> $field = $web.Fields.GetFieldByInternalName(<field name>) $field.Type = [Microsoft.SharePoint.SPFieldType]::MultiChoice $field.Update($true)
Is there a Calculated column that uses the value of this Choice column? It looks like Calculated columns can't reference Choice (checkbox) columns in their formulae, so if an existing Calculated column is currently referencing the Choice column, you're prevented from changing the Choice column's type to checkbox so as to avoid breaking the Calculated column's formula.
Remove the Choice column from the formula of any Calculated column in the list, then try to change the Choice column's type to "checkbox" again.