> but 56k was fine over regular lines.

Sort of. The quality/length of your local loop made a difference.

And heck, 56k being able to do 56k in the first place was dependent on not having a "regular" line between the ISP and their central office (CO), but rather it being digital, whereas the line from the user to their CO was always analog. Removing a set of digital to analog and analog to digital conversions in the ISP -> user path was what allowed the download speed to reach 56k. Upload was limited to 33.6k because it included an additional set of conversions and introduced more errors, prohibiting the higher speed.

This shows getting up to 56k over normal phone lines was indeed tricky.