Protect and Fake Out never had the same priority.
Prior to Generation V, Fake Out and Protect was +1 and +3, respectively.
Post Generation V, Fake Out and Protect was +3 and +4, respectively.
So yeah, Protect would still go first.
Hope I helped. :)
Source: Bulbapedia's Fake Out and Protect pages