Actually, this is not related to subst:

(%i1) p = not q;
incorrect syntax: Found logical expression where algebraic expression expected