It's also worth pointing out that using Elpar in rules is very unreliable and not really recommended (by me anyway

) This is because of the index in the function and the multiple hierarchies in the dimension. There is no way to control which hierarchy is "2" and just because the hierarchy for one element is "2" this does not mean it will be 2 for all elements in the dimension. As well as that problem it's not stable and I have seen the hierarchy that was "1" become "2".
Setting up the attributes is the way to go. It should make the rule faster too.
That said your rule looks wrong, did you mis-paste it?
['New Employees']=N:DB('New_Headcount_Cost',!Department,!Year,!Version,'Month');
Should just work. Even though Department is not in the in the headcount cost cube, the N levels of Department are in the Titles dimension so the match will still work. I think that you would need to put more elements on the left of the rule to specify what is happening with the shift and month dimensions.
The problem you will have is with the feeder from the Headcount cost cube, since feeders only operate at the N level and the N levels of Title are not in the Department dimension the feeders will fail. This is where you need to use Elpar or an attribute.
In the Headcount cost cube you would have something like.
['Month']=>DB('Employee Headcount Measures', Attrs('Title', !Title,'Department'), 'Hardcoded reference to shift',''Hardcoded reference to month', !Year, !Version, 'New Employees');
Hope this gives you an idea of what to do, that’s if I’ve not got the wrong end of the stick.
Cheers