Are you testing this in Production or Sandbox? Scheduled workflows and workflow actions won’t run in sandboxes (SuiteAnswers 19470).

If you’re in production and this still isn’t working, my suggestion is the same as @jarens mentioned, if you can share the detailed workflow logs from a record that is stuck we might be able to help you figure out why NS is ignoring it (you’ll need to make sure that Logging is turned on in the settings for your workflow).

Does the role have Publish Search? That controls search edit rights as well as some other stuff (setting up alerts, scheduled sends, etc). Try removing that and see if they can still edit.

There is an open enhancement request around this, you can’t edit admin users as a non-admin, even with permissions set to Full. The details are under SuiteAnswers 73725, but the solution is to have an admin change/manage the data for other admins, or assign the HR person the admin role.