We present results of targeted searches for signatures of non-radial oscillation modes (such as r- and g-modes) in neutron stars using {it RXTE} data from several accreting millisecond X-ray pulsars (AMXPs). We search for potentially coherent signals in the neutron star rest frame by first removing the phase delays associated with the stars binary motion and computing FFT power spectra of continuous light curves with up to $2^{30}$ time bins. We search a range of frequencies in which both r- and g-modes are theoretically expected to reside. Using data from the discovery outburst of the 435 Hz pulsar XTE J1751$-$305 we find a single candidate, coherent oscillation with a frequency of $0.5727597 times u_{spin} = 249.332609$ Hz, and a fractional Fourier amplitude of $7.46 times 10^{-4}$. We estimate the significance of this feature at the $1.6 times 10^{-3}$ level, slightly better than a $3sigma$ detection. We argue that possible mode identifications include rotationally-modified g-modes associated with either a helium-rich surface layer or a density discontinuity due to electron captures on hydrogen in the accreted ocean. Alternatively, the frequency could be identified with that of an inertial mode or an r-mode modified by the presence of a solid crust, however, the r-mode amplitude required to account for the observed modulation amplitude would induce a large spin-down rate inconsistent with the observed pulse timing measurements. For the AMXPs XTE J1814$-$338 and NGC 6440 X-2 we do not find any candidate oscillation signals, and we place upper limits on the fractional Fourier amplitude of any coherent oscillations in our frequency search range of $7.8times 10^{-4}$ and $5.6 times 10^{-3}$, respectively. We briefly discuss the prospects and sensitivity for similar searches with future, larger X-ray collecting area missions.