Maybe it's a little late to tell you, but I managed to speak to Apple Care in the UK yesterday who are arranging to send out a replacement set of buds for me (for free it seems).
Odd way to do things, but I had to give my iPhone serial number to them (worryingly is was register to someone else - which considering it's mine and was new on release day is a bit strange). They really seem to have no real idea about these buds, but if you stick it out you can get them to send some out. The truth about mine is the small buds had become loose and thy pop off if brushed up clothes easily. I found it bizarre that they are sending them out via UPS!
If your sorted then sorry to bring up the old thread, however it might be useful for others
Called Apple again, seems they are sending me a complete replacement set of headphones. Sound like a retail box as well. Which is very nice, but seems over the top. Still can't complain as it means I'll get a spare set of headphones as well