Your contract is apparently with Vodafone, so any responsibility lies with them to resolve. But having said that, they have suggested that some of the problems might be out of their contract terms, by stating what they have?.
You could contact Nokia (having been suggested by Vodafone!) or your local CAB http://www.adviceguide.org.uk for help and advice?.
Consumer Direct who use to deal with these issues, no longer exists, and CAB have taken over the role regarding consumer advice issues.