Alright... I got it and it works. These are the steps I took:

1. Used App Loader to remove (delete) BB Messenger from my phone
2. After deleted, used App Loader to install it again
3. At this point, the Messenger program is totally new and empty. So I used the Backup/Restore application to Restore only the BB Messenger files

And it's back to perfect again... with the v4.5 Messenger and all my contacts/settings.

** The backup file I used to restore the Messenger info was one from BEFORE my OS update. I dunno if it makes a difference but I thought that would be safer.