I've contacted the NCA and will see what they say.
mercman, there is no point contacting Apple, the letter is a photocopied standard issue, so they obviously believe they are within their rights to send a refurbished model.
On closer inspection, the replacement iPod I received has its safety message on the back in French, so I'm not actually sure if they sent a new or refurbished one.
emaol - That is what I'm asking, are they entitled to fob you off with a second-hand iPod when the brand new one you purchased never worked. They obviously seem to think they are.