Making iMessage work

After updating not jailbroken and not carrier-locked iPhone 3GS to 6.1.6 I couldn't activate it.
So I went through some sort of redsn0w hell and now I have jailbroken 6.1.6 with 05.13.04 baseband and an ultrasn0w unlock, which makes the calls work.
However, iMessage won't activate saying there are connection problems and the push-notifications are broken.
So my question is: should I try using SAM and how risky is that? Because I don't want to go through the jailbreaking process again for nothing.
Also, the guy who posted a video describing the jb process advised using Handcent SMS instead of iMessage, but unfortunately it sent me only a couple of messages and now it only receives them, and doesn't send.