Identifying the start time of a sequence of symbols received at the receiver, commonly referred to as \emph{frame synchronization}, is a critical task for achieving good performance in digital communications systems employing time-multiplexed transmission. In this work we focus on \emph{frame synchronization} for linear channels with memory in which the channel impulse response is periodic and the additive Gaussian noise is correlated and cyclostationary. Such channels appear in many communications scenarios, including narrowband power line communications and interference-limited wireless communications. We derive frame synchronization algorithms based on simplifications of the optimal likelihood-ratio test, assuming the channel impulse response is unknown at the receiver, which is applicable to many practical scenarios. The computational complexity of each of the derived algorithms is characterized, and a procedure for selecting nearly optimal synchronization sequences is proposed. The algorithms derived in this work achieve better performance than the noncoherent correlation detector, and, in fact, facilitate a controlled tradeoff between complexity and performance.