Hi, It's giving you this error because you're in an After Update trigger on Account, e.g. in this transaction an Account has already been updated and now you are trying to update a User.   (Go to the Help & Training popup in the UI and type in Mixed_DML_Operation and it will give you the doc on it.)  

Either way, I think you are going down a wrong path.  I think you should reparent the Contacts to active users.

But first, just fyi, I cleaned up your first attempt (which was pretty good).

trigger UpdateChildObjectsToDepartment on Account (after update) {
  // We are changing Accounts from Companies to Departments.  
  // We want to change all Contacts who are "in" those Department Accounts such that their  
  // 1. new Department Id now points to the Account we are changing, and 
  // 2. their new Account Id points to the Parent of the Account we are changing.

  Map<Id, Account> accountMap = new Map<Id,Account>();

  // Gather all the Accounts we're converting to Departments
  for (Account a : trigger.new)
     if (a.Department__c && !trigger.oldmap.get(a.id).Department__c) accountMap.put(a.id, a);
  
  if (accountMap.isEmpty()) return;
      
  // For each Contact in those Accounts....
  // There may be many children, process them in bulk...
  for (Contact[] children : [
      SELECT f.id, f.Accountid,  f.Owner.Name, f.Department__r.id, f.Ownerid, f.Owner.IsActive
      FROM Contact f
      WHERE f.Accountid IN :accountMap.keySet()]) {
        for (Contact child: children) {
            child.Department__c = child.Accountid;
            child.Accountid = accountMap.get(child.Accountid).Parent_Company__c;
        }
      update children;
  }
}

Now, this will fail for the cases where the Contact Owner is inactive, I think the explanation for what you see is:

-----------------------------------------------

Update Unsuccessful  The record owner is inactive.  Before you can make this change, assign this record to an active user.

This message will occur whenever two related records are owned by different users, where the child record owner is inactive, and the user tries to change the parent record.  As an example, Account A is owned by Active User 1 and Contact B is owned by Inactive User 2.  If you try to change the parent Account on Contact B, you will receive an error.

This is because when the owner of a child record is different from the parent, we create an implicit share on the parent record to provide access.  When we deactivate the user record, we retain the existing shares on the record, including the deactivated user (even if they can’t login any longer). However, when you try to transfer the child record to another parent, we try to add an implicit share to the new parent, which we can’t do since the user is now inactive and no new shares may be created for the inactive user (only existing shares are retained). As a result, you will be prevented from reparenting the child record until you change the record ownership to an active user or you reactivate the user.

-------------------------------------------------

 So, the path you're on is to split the children Contacts into two groups, those with Active owners which you can just update in the trigger, and those with inactive owners.  And, for the inactive ones you want to 

1. Reactivate the User,

2. Do the updates for that users Contact(s)

3. Deactivate the User.

It would be sweet if you could just select all the users, set them all to active, and then update them all at once, do all the Contact updates, and then deactive all the users.  And, if you only have a few users you might be able to get away with that.   However, if you have a lot of Users impacted, then you could use a bunch of your Salesforce licenses all at once and that becomes a different problem.  So, you probably want to do that one at a time?  And it has to be in an @Future method, because you can't mix the DML, etc. within one trigger.  This turns into a real pain.

So, the thought that comes to mind and makes me think you're going down a bad path is: why are you going to allow Contacts to be owned by Inactive Users if you are bothering to update them?  Why not re-parent them to the owner of the Account?  Isn't it just sort of questionable data modelling to update data with no sort of ownership of the data?    OR  

Just decide that the Contacts with Inactive Owners won't get updated.

I mean you're left with some ugly options...   If you really want to push all the user, contact, and contact update information into an @future class, cycle through the users one by one, and do the updates, you probably could.  But I don't think it's a good solution.

Is there any better path from a business analysis perspective to model what you need?

Best, Steve.