What is the resolution of your GIFs? Ideal size for Pic messgs. is 128*128. Only then can a MMS editor handle them .
If GIFs aren't animated, better you convert them to jpeg format. There are many tools available for this, IRFAN View is one good program and viewer to do this conversion. Then try sending them once again. I don't know much about nokia software but I think you can send picturemessages by selecting the picture you want to send as MMS and select send>via picturemessaging.