Orthogonal frequency division multiplexing (OFDM) and multiple access (OFDMA) signal receivers often employ pilot-aided channel estimation. For it, an often considered technique is frequency-domain polynomial interpolation, due to its simplicity. However, the performance of polynomial interpolators suffers in channels with large delay spreads due to modeling error. The problem can be remedied by including a linear phase to the interpolator. In this paper, we derive a method to estimate the optimal phase shift that minimizes the mean-square channel estimation error. We further consider adaptive selection of the interpolation order for best performance. As a practical application, we adapt the proposed channel estimation technique to Mobile WiMAX downlink transmission and examine the resulting performance.