In this paper, we consider the frequency offset estimation for Orthogonal Frequency-Division Multiple Access (OF-DMA) uplink (UL) transmissions. We first analyze the negative effect of Multi-Access-Interference (MAI) on OFDMA UL, and then propose two interference reduction/elimination methods, i.e., the Reduced-Rank-Projector (RRP) and Shift-Sampling-Projector (SSP) methods, to eliminate/reduce the heavy MAI due to the frequency offsets. Finally, we propose a new training sequence group named the Round-Robin Training Sequence Group (RRTSG), which has a high interference mitigation capabilities for OFDMA UL transmission. The Cramer-Rao Lower Bound (CRLB) for an unbiased frequency offset estimator in a Multiple Access (MA) system is also derived. Numerical results show that the proposed methods are suitable to eliminate/mitigate the effect of the frequency offset on OFDMA UL transmission.