Re: The ICO is toothless
"I changed my phone number and less than two weeks later they were back using my name on the new number."
Obvious questions: Did you have your new number unlisted? If not - they used the phone book.
If the number is unlisted, have you phoned a company from that number without withholding it? Or has anyone else? If so, they know who you are and could have retained the number.
If you haven't, have you registered the number anywhere against your name? This includes banks. If so, then someone traded your number.
When you answer the phone (or anyone at that address for that matter including a telephone answering machine message) do you announce who you are? If so, they could be random number dialing and recorded the name given when you, someone else, or the answering machine gave it. They might even have asked (possibly in response to a demand to remove your number from their system).
The moment one company has your name and number, they'll share/sell it on and then you'll get more calls, all claiming they're allowed to call.
If you've done none of the above then they shouldn't have your name againt that number at which point I'd refer it to your Tel-Co to explain. But be absolutely certain you've not fallen foul or slipped up even once with the above as your Tel-co will insist you must have.
However, if it was the Tel-co who gave out your details, it could have been under the pretense that the company was running a poll on behalf of the government and so was allowed even unlisted numbers. This is the excuse I had from one company who got my unlisted number. They were lying, of cause: I followed up with enquries of my own (aka a FoI to the relivant department on telephone polls they had commissioned in the last few years - their reply was they hadn't and wouldn't run such a poll). Cue one more complaint to OfTel.