Telco's encode their data as 8 bit samples, at 8khz. Which if you do the math is 64kbit/s.

They then transmit several channels down one line, where there is 8 bits of one channel, then 8 bits of the next channel etc. To syncronise, they set all the low bits to 0, except for the first channels which is set to 1. When one of the ends starts up, it reads the line reading 8 bits at once, expecting to see in the low bit a "1" every "nth" sample and 0's inbetween. If it doesn't see this pattern, it "drops" a bit, and tries again until it gets the right pattern (and therefore a lock.)

However this means that you lose the low order bit of your transmissions, so you only have 7 bit samples at 8khz which works out to being 56kbit/s. And that is why your modem can only get 56k, and only when the remote end has a digital modem.