AND(OR( AND( NOT(ISCHANGED(Status)),
OR( ISPICKVAL(Status, 'Complete'),
 ISPICKVAL(Status, 'Completed') ) ),
 AND( ISCHANGED(Status),
OR( ISPICKVAL(PRIORVALUE(Status), 'Complete'),
 ISPICKVAL(PRIORVALUE(Status), 'Completed')))))

AND(
  OR(
    ISPICKVAL( PRIORVALUE(Status), 'Complete'),
    ISPICKVAL( PRIORVALUE(Status), 'Completed')
  ),
  NOT( ISNEW() )
)