[SalesForce] validation rule on multi select picklist at least one select

What you're asking can't be accomplished through a validation rule, without hand coding every value like you suggested.

On the other hand this could very easily be accomplished with a before update trigger that looks something like this:

trigger MyTrigger on MyObject__c (before update)
{
    //this variable could also be gotten through use of the system describe methods
    Integer totalPicklistItems = 30;

    for(MyObject__c obj : Trigger.new)
    {
        if(obj.MultiSelectField__c != null && obj.MultiSelectField__c != '')
        {
            //split picklist into list
            String[] selectedValues = obj.MultiSelectField__c.split(';', 0);

            //check if the selected selected values are less than 1 or equal to the
            //total picklist items to add an error
            if(selectedValues.size() < 1 || selectedValues.size() == totalPicklistItems)
                obj.MultiSelectField__c.addError('You must select at least 1 value but not all values.');
        }
        else
        {
            obj.MultiSelectField__c.addError('You must select at least 1 value.');
        }
    }
}

You can't use multi-select picklists with ISPICKVAL. Instead, you need to use INCLUDES. The Documentation describes its use as follows:

INCLUDES(multiselect_picklist_field,text_literal) and replace multiselect_picklist_field with the merge field name for the multi-select picklist; and replace text_literal with the multi-select picklist value you want to match in quotes.

So your formula should look something like this:

AND(
 $Profile.Name = 'System Administrator',
 ISPICKVAL(Status, 'Career Advisor - Inbound'),
 ISBLANK(other_explanation__c),
 INCLUDES(multi_select_picklist__c, 'Other')
)