Most ADSL offerings these days are 'rate adaptive' - they train to the highest speed possible on your telephone line. BT offers their ADSL MAX product which will give speeds up to 8Mbit/sec depending upon line length & quality.
Unfortunately some very long or poor quality lines just cannot support this service and ADSL will fail to synchronise even at 512kbit/sec. Sometimes the BT Home 250 product which is tied down to working at 250kbit/sec will work on these lines. It is possible that if the Home 250 service works then line statistics can be measured and it may be possible for an ISP to get enough information about your line to make some improvements with BT and achieve an upgrade to 'full' ADSL.
Home 250 is supplied by the following ISPs and probably a few more besides.
Andrews & Arnold
Zen Internet
Merula
Zetnet
