iMessage won't work. ("Not Delivered")

I installed iOS 5 yesterday both in my granpa' iPhone 4 as in mine. But, we have a problem, as he can send iMessages, can use FaceTime and everything else, my iMessage app always shows a "Not delivered" sign, a second right after press send, under the text..

I mean, the text is never sent, nor as an iMessage (which is baaaad), or as a normal sms (which is confusing, with me having activated the option at Settings).

The fact is that I have multiple Apple accounts, although I would like to not, but the destiny had droven me to that faith (can that be said that way? xD).

Anyway, I wanted to know if this had happened to somebody else, and, mostly to know if there is a solution. And no, I already tried to turn on/off imessages AND facetime, and that only made me spend all the credits I had...

I already tried to use another apple account, nothing. I reboot the idevice, nothing. I reboot the pc, and restore the idevice, nothing. Nothing had worked so far, so I wanna know, because the only reason I upgraded was because of the iMessages (and all the rest, but mostly 'cause the iMessage feature).

Just to prevent you to ask, I have high speed wi-fi (moddest speed, as I'm in Venezuela....) and I tried as well on 3G, EDGE and even other wifi zones, and still, my grandpa' won...

PD. I just tried out the Find My iPhone feature: IT DOESN'T WORK EITHER. Really, I love apple, but you really messed this up this time.