This paper proposes an efficient motion re-estimation using enhanced predictive zonal search (EPZS) algorithm for H.264/AVC video downscaling transcoding to reduce computation cost while maintaining high coding performance. Three prediction motion vectors (PMV) using AAW, ABW and AWW approaches are defined based on CBP and MV information in original H.264/AVC coded videos. The proposed EPZS takes into account four MV predictors (including AAW, ABW and AWW predictors as well as median predictor defined in H.264/AVC). The experimental result reveals that the proposed EPZS algorithm achieves a significant reduction of 66% computation time while maintaining coding efficiency as good as fully decoding and re-encoding. The result also shows that the proposed algorithm outperforms the AWVM algorithm in all respects, including PSNR, bit-rate increment as well as computation saving.