[SalesForce] Validation Rule for Changed Value

Try this:

AND( ISPICKVAL( PRIORVALUE ( Advancement__c), "Stage 1"), ISPICKVAL(Advancement__c, "Stage 3"), NOT ($Profile.Name = "System Administrator") )

There's a conceptual issue here

Validation rules fire upon DML of an object (insert or update). The VR has access to the before and after values of the object (update use case). But lookup fields are in different SObjects and those aren't undergoing DML when the VR on your target object is executing. Hence, PRIORVALUE and ISCHANGED on lookup fields won't get you what you want.

The formula fields on the target object do get evaluated on the before and after values.

That said, when DML on an object executes, the only thing that can possibly change with regards to the lookup objects is the foreign key itself. So, perhaps your application can detect changes in the foreign key (lookup field) and use that for your checks.