Very interesting i'm having the same issue with one of my two telus devices. Both storms. It says my contacts are "unreachable". My contacts are with a couple different providers as well. I've tried "pin"ing one or two a message with no response.
I just got a new device with a fresh OS on it so I thought it might be related to the new pin number.
I'll try using my BBM options file from an older back up file and see if that helps. Otherwise i'll call telus later this morning and see what kind of answer they give me.
Bellshare - Premium Blackberry Apps