After working great for a few minutes the data stopped working.
The H icon showed that traffic was sent from the phone but no traffic received by the phone.
Sometimes the data connection was restored by itself and sometimes I has to toggle the data connection off/on to have it restored.
It both cases the data connection failed again after several minutes.
All the diagnostics app showen that there was hspa connection.
After trying almost anything I could think of I found out what causes my problem:
It's the F**** NFC!!!
I've forgot that a week ago I've disabled the NFC thinking this will save battery life (though the battery life is great).
Turning the NFC on (followed by a power-down/power up cycle) solved all the data connection problem.
I've verified several times that NFC disable is indeed the cause of my problem.
Hope this helps others on this thread.