Here are a couple of things to try.
1) Since it is PPPoE try changing the MTU size. Try 1000 first but you might need to play around with it
2) Change the NIC card. I have seen this behavior with a NIC card that was having problems. The system could connect fince but VPN, file sharing, etc would not work. Since you changed providers I would look at the hardware first but did the service actually change or just who you paid the bill to? Proider B could just be reslling Provider A's service