Nice! That sure worked. I had to add all of them one by one, which took me a couple of hours, but all my contacts can now add any custom emoticons I have.
I guess using MSN BackUp isn't such a good idea if you want your friends to be able to add your stuff.
Thanks a lot!