Recently took BT three weeks to solve this problem for me. Combination of noise and DACS (multiplexing unit) fitted by BT to save money (for them!) was cause. Report it as fault to BT and keep at them!
PhiltheFragger, I'm on NTL BB and I also get 'no internet connection is available.' when I open Mailwasher for the 1st time. I find that if I then open Firefox, wait for it to connect to the net and then open Mailwasher it connects fine.
I thought it was just a glitch in the program. I'm not sure if it can be noise for me because I'm on cable. Also using a wired router and XP home.