T-Mobile is currently experiencing a known issue with this. The IM application downloads through OTA and for some reason the service books is not tripping that download. So even though you have the IM icon, the IM application is not installed. So far T-Mobile doesn't have an ETA for when this issue is going to be resolved.
To correct this issue when it does get fixed. Delete the T-Mobile USA IM Client service book and then register in the host routing table. That will force the service book to download again and hopefully install the IM application.