I agree it sounds like a noise issue. What I've done in the past is I had the phone company test the line for noise level. Mention to them that you need a "clean pair" for your modem.
Also, make sure all your cables and connection points are in good condition.
With a 56k your speed setting should at 57.6K or one step higher never lower. The modem will automatically select the speed that works best. In KPPP select configuration and the modem tab and you should be able to edit the modem parameters.
HTH