With the animation, it may be the number of frames.. Sometimes this can cause a problem. Or try re-starting ur MSN then adding them again. Would you mind showing us the animated emoticons you are trying to add?
And there is something I have that can get emoticons and things off ur computer.. In the right file type. It was in a thread somewhere. I'll try to find the thread, otherwise i'll have to try and send you the program and hope it works.
EDIT:
Ah yes, I found it.
Read:
http://shoutbox.menthix.net/showthread.php?tid=38216&page=1
/ 
