Ok, I think I figured it out. I narrowed it down to the users.sls file. Once I removed "users" from top.sls, the problem went away. But, I need users.sls to create the proper users.

My Vagrantfile is set up to automatically create the initial user accounts and set the authorized_keys file, but I was incorrectly setting the group of the users to "sudo", rather than the default group.

I think the problem was that salt was changing the user group based on my state files, and after it switched the group, for some reason it ended up thinking that it didn't have any states to execute. Again, once I rebooted the minions highstate worked again.

I've fixed it by having the users added properly in the Vagrantfile.

Vagrantfile BEFORE:

users = {
    "dave" => "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA==",
}
$script = ""
users.each do |key, val|
  $script << "sudo adduser --ingroup sudo --disabled-password --gecos \"\" #{key}\n"
  $script << "echo \"#{key} ALL=(ALL) NOPASSWD:ALL\" > /tmp/#{key}-sudoers-nopasswd\n"
  $script << "sudo cp /tmp/#{key}-sudoers-nopasswd /etc/sudoers.d\n"
  $script << "sudo mkdir /home/#{key}/.ssh\n"
  $script << "sudo chown #{key} /home/#{key}/.ssh\n"
  $script << "sudo chmod 700 /home/#{key}/.ssh\n"
  $script << "echo \"ssh-rsa #{val}\" > /tmp/authorized_keys\n"
  $script << "sudo cp /tmp/authorized_keys /home/#{key}/.ssh/authorized_keys\n"
  $script << "sudo chown #{key} /home/#{key}/.ssh/authorized_keys\n"
  $script << "sudo chmod 600 /home/#{key}/.ssh/authorized_keys\n"
end
Vagrant.configure(2) do |config|
  config.vm.box = "ubuntu/trusty64"
  config.vm.provision "shell", inline: $script
end

Vagrantfile AFTER:

users = {
    "dave" => "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA==",
}
$script = ""
users.each do |key, val|
  $script << "sudo adduser --disabled-password --gecos \"\" #{key}\n"
  $script << "echo \"#{key} ALL=(ALL) NOPASSWD:ALL\" > /tmp/#{key}\n"
  $script << "sudo mv /tmp/#{key} /etc/sudoers.d\n"
  $script << "sudo chmod 440 /etc/sudoers.d/#{key}\n"
  $script << "sudo mkdir /home/#{key}/.ssh\n"
  $script << "sudo chown #{key} /home/#{key}/.ssh\n"
  $script << "sudo chmod 700 /home/#{key}/.ssh\n"
  $script << "echo \"ssh-rsa #{val}\" > /tmp/authorized_keys\n"
  $script << "sudo mv /tmp/authorized_keys /home/#{key}/.ssh/authorized_keys\n"
  $script << "sudo chown #{key} /home/#{key}/.ssh/authorized_keys\n"
  $script << "sudo chmod 600 /home/#{key}/.ssh/authorized_keys\n"
  $script << "sudo chmod 750 /home/#{key}\n"
  $script << "sudo chgrp #{key} /home/#{key}/.ssh\n"
end
Vagrant.configure(2) do |config|
  config.vm.box = "ubuntu/trusty64"
  config.vm.provision "shell", inline: $script
end