When I cannot get a substitution to work I look at the
FullForm of the expression.
FullForm[a0+3 a1 y(1+x E^(I 3 q)+E^(-I q+2 I p))==0]
which shows me
That can sometimes surprise you that the internal form is somewhat or even quite different from the pretty printed version on the screen. I write my substitution to exactly match that internal hidden structure.
The first substitution you wanted appears to be
a0+3 a1 y(1+x E^(I 3 q)+E^(-I q+2 I p))==0/.Power[E,Times[Complex[0,n_],q]]->z^n
a0 + 3*a1*y*(1 + E^((2*I)*p - I*q) + x*z^3) == 0
That worked on the first try.
Well, actually, to be really honest, I tried to do both your substitutions at the same time and the second substitution was somewhat different and I didn't succeed with that on my first try.
Can you study what I did here and try to understand the strategy and use this method on similar problems and get the substitution to work on the first try? And then can you look at the second substitution that you want and see if you can understand how to use this to make that substitution work?
Hopefully this method can help you solve substitution problems that don't work for you.