Now the user turned out to be new and that was a big clue.
I got this error of openmsg store failed 0x8004011d. I actually forget whether it was on the device or in the log files on the Blackberry server. I think it was the latter.
In any case, the fact this user was new was a big clue. In Exchange 2010 (and possibly other versions), you have to enable Blackberry communication on the store level. This new person was in a newly assigned store where we had forgot to make this critical configuration change.
It was a simple change in the end and after that, the activation worked!