If you have a noisy line then your modem will constantly go in and out of synch - ie you will keep losing your connection. When BT turn interleaving on it uses an error correction routine to stabilise the line so you will stay synch'd but probably at a lower speed. This doesn't seem to be your problem as I'm assuming the line is stable when you get connected. See here for a layman's explanation of how broadband works:
http://www.aaisp.net.uk/maxmagic.html
Have you tried connecting using someone elses laptop to rule out your computer as the problem? What model of modem are you using now?