It sounds like your using a DSL Line, you could try checking your MaxMTU Settings. If your previous provider was Cable, your ideal MaxMTU should have been 1500, Now that your on DSL [PPPoE ?] Your MaxMTU should be set to 1492.
You can use a tool called TCP Optimizer from
www.speedguide.net to adjust this and all of your other relevent TCP/IP Settings.