First read you contract, see what level of service they guarentee.
Don't forget most home ADSL is at 50:1 contention so you are only paying for 512kbps/50 users which equates to about 10kbps.
Do you have, or can you compile, a record of when you have contacted them to complain about the service? (If not do so, collect ping stats screen grabs of speed tests, times of failure s that you can prove are thiers not the site that you are visiting.)
If so and they have had say a month to improve the sertvice since your first couple of complaints I would write to them, say you are terminating the contract with XX days notice for non performance on thier part, documenting the faults and when you reported them and send it recorded delivery. Cancel you payment after XX days.
Worst case as far as I can see they persue you for the 12 months fee so you give in and go back on the contract. Best case they accept the termination.
Although Ao'hell do do some strange things with images and proxy servers etc. If it is just the ADSL speed that is the problem as I understand the ADSL system (ready to be corrected!) you may not get a faster connection through the same exchange.