Modems, methods, and computer program products for falling back to a low speed mode of operation upon detection of abnormal line conditions during startup perform a first phase of a multiphase startup procedure in accordance with a high speed mode of operation. A determination is then made whether the line conditions will support high speed communication. If a high speed connection cannot be established, then subsequent phases of the startup procedure will be performed in accordance with the low speed mode of operation. Otherwise, subsequent phases of the startup procedure will be performed in accordance with the high speed mode of operation. By detecting abnormal line conditions, such as digital discontinuity, severe attenuation, or a local loop having a non-linear frequency response, early in the startup protocol, the remainder of the startup protocol can be performed in accordance with a low speed more of operation as the detected abnormalities in the communication path will prevent the establishment of a higher data rate connection. Accordingly, the reliability and efficiency of the startup protocol are improved.