Should be no need to delete the messenger. Uncheck the Remember Me and Auto Sign In features, clear your cookies, then try logging back in again.
Worked for me.
But, as noted above, there have been cases where deleting and reloading the YM was necessary.
And if this is the case, here's a link for you.
Posted from my CrackBerry at wapforums.crackberry.com