Im having the same problem with WLM and AIM, no issues with YM. I've been all day with T-mobile & the Blackberry customer service.
A person on the blackberry department told me that, is Tmobile that should "unblock" the service permission for the instant messenger and everything else looks fine for the data service. Then he recomended me that I should downgrade my software to their 3 year old tmobile crap
Like if that is going to resolve the issue