"Connection speed and how to improve it" question...

Howdy Folks!

Sheesh...for years I've been stuck with Dial-up but it was perfectly fine until recently. I used to connect at 34-38Kbps but all of a sudden (two weeks ago) I am unable to connect any higher than 26-28.

I've had the phone company out here checking my lines this past week but they couldn't find a problem at their end of it. (In the past when I've had excessive line noise the phone tech would easily amend something at the connection box out on the road and it would resolve the problem. There is no line noise this time, just slow connection speed.)

I've check my phone line cord connections, etc, and everything looks tight and well-connected. Recently (a month or so ago) I put in a new modem because I thought the other one was shot (I couldn't connect but later found out it was a glitch in my power/phone surge protector that was keeping me from connecting).

Question: Would the modem itself come into play as far as connecting as it should? (I have a 56K modem.)

Does anyone have any ideas as to what other areas I can cover to regain my connection speed?

Many thanks!
Shoe

(and no, we don't have DSL available here yet or I would certainly go that route.)