To debug your problem I would do following:

-Does it happen also when you are connected to wifi?
-What is your online status when you are trying to send messages? (away,invisible,online..)
- Do you use 3g or 2g?
- Does these problems happen in certain place?