How to estimate the voltage gain, Input impedance, current gain, power gain, and output impedance for the amplifier in the fig?
From the problem description looks like two problems. First with Re fully bypassed and Second with only part of Re bypassed.
Start with fully bypassed. 
re=.026/4.12e-3=6.25 Ohms making hie about 635 Ohms. This will make Zi (looking to the right of the coupling capacitor) 635||5k||10K~533 Ohms and not what you calculated.
Vs sees 500 Ohms in series with Zi, a voltage division of Zi/(500+Zi)--> 0.53*Vs at the base of the transistor.
This makes base current Vb/hie=Vb/((beta+1)*re) and collector current -Beta times this or 
ic~-vb/re=-0.53*Vs/6.25=-Vs*84.8e-3 and the voltage transfer function H=ic*Rc=-84.8*Vs

So comparing your results with these I see 1)re incorrect and 2) voltage gain is from vs, not vb so that there is a voltage division factor missing in your Av equation.