While http://www.wayne.hardy.com/ covers a lot of the topic, you have to pester who owns the lines from your house to the next box to get it fixed. There are a few tests you can do. Such as unplugging everything on the line, go find the junction box and giving the terminals a slight tightening, then retesting.

It's also possible your new ISP is at odds with your settings, but you'll have to chat with them about that.