Wol, I've been through this before and I know that it can be a worry.
I had my identity stolen by someone who took out two mobile phone contracts in Bromley (a place I generally avoid) a few years back. What you have done is correct and there is not much more that you can do. It is unlikely that the bailiffs will be sent but you do have to get reassurances from the supermarket bank that this is a case of identity theft and that they should not use this mis-information to affect your credit rating in any way.
My case was resolved because the criminals gave a wrong middle name and date of birth on their forms. It is likely that the person who used your details also did this. It's easy to get a name and address from a telephone directory but they have to guess about more personal details. I was slightly shocked that the police were not interested - apparently identity theft does not imply that someone has stolen anything from me. They would have been interested if the phone shop had reported it, as it had suffered a loss through fraud.
Initially, the phone shop wanted me to send a copy of my passport and a sworn letter saying that it was not me. I refused to do this because of the cost and the potential for personal data going astray again. In the end, they sent me a letter which I had to sign and return confirming that I had not taken out the two contracts.
The bottom line is to have a written audit trail pointing out that the error is theirs and that you are the victim of identity theft. You could call them to make sure that they understand this. Good luck