It's not totally beyond to think that during installation of next-door's broadband that they might have somehow managed to damage your telephone cable - or in some way 'dislodge' the connections, etc., etc.
Sadly, I don't think you really have a leg to stand on - as long as you can connect, I think that's really all you're going to get. I believe - at one time, on BT - there was some sort of regulation that stated that a connection of at least 16kbps should be available.. and you're getting a lot more than that and on cable!
