I live in Bristol and have broadband with Telewest, which is the local cable tv company.
I pay about £25 for the .5 Mbps service. They also have a 1 and 2 meg service at about an extra tenner each time.
I'm pretty sure Telewest are available throughout the BS area but a check on their web site will verify as they have an engine which checks postcode against availablity.
It is worth the change, the download time is very fast and my partner (Flemish) can now listen to her favorite radio stations while she surfs.