I wouldn't rule out exchange problems with behaviour like that.
Seems unlikely as the performance on O2 was fine. We may have swapped ISPs but it is the same line running at the same speed on the same exchange. Seems highly unlikely that the exchange would suddenly develop a random issue when we swapped ISP. But I guess it could be.
On a completely unrelated note someone needs to do something about the pushy guys from talktalk that keep on coming round our area and spreading lies to people about how they are paying for broadband when they should be getting it for free. They ask people what ISP they are currently on and if they can do line tests and promise they can get you out of your current contract and give you a free service. Sounds like total BS and is very aggressive marketing.