Testing with phase-randomised surrogate signals has been used extensively to search for interesting nonlinear dynamical structure in experimental time series. In this paper we argue that, in the case of experimental time series with strong periodic components, the method of phase-randomised surrogate data may not be particularly suitable to test for nonlinearity, since construction of such surrogates by FFT requires a time series whose length is a power of 2. We demonstrate that, in the case of (nearly) periodic signals, this approach will almost always produce spurious detection of nonlinearity. This error can be fixed by adjusting the length of the time series such that it becomes an integer multiple of the dominant periodicity. The resulting time series will not be a power of 2, and requires the use of a DFT to generate surrogate data. DFT-based surrogates no longer detect spurious nonlinearity, but cannot be used to detect periodic nonlinearity. We propose a new test, nonlinear cross-prediction (NLCP), which avoids some of the problems associated with phase-randomised surrogate data, and which allows reliable detection of both periodic and aperiodic nonlinearity. In the test the original data are used to construct a nonlinear model to predict the original data set as well as amplitude-inverted and time-reversed versions of the original data. Lower predictability of the amplitude-inverted or time-reversed copies reflect, respectively, an asymmetric amplitude distribution and time irreversibility. Both of these indicate nonlinearity in the data set.