Live Messenger Upgrade and Custom Emoticons

I upgraded from Messenger 9 to WLM 8.1.0178.00. When I did this I found that
my custom emoticons had disappeared. Some were copied form people who sent
them to me in a conversation and others I added from Gifs on my local disk.
When I attempted to add the emoticons again I get the following error:
The image you choose is already being used for another emoticon. Please
choose another image.

I have now figured out that this occurs for custom emoticons I already had
in place. I can add new custom emoticons that I have never had before.
Renaming the emoticon Gif file to something different has no affect, I still
get the same error message. If I get sommone to send me an emoticon I copied
from a conversation in the past I can still add that one with no errors.
Can anyone tell me how to access the missing emoticons, or how to delete the
custom emoticon information so I can set them up again from scratch?

Thanks,
Chris