I had the same issue on my phone but it happened after i replaced the SIM card.
It was the carriers problem. On their backend system (PDA/BB support was only able to access that system), the caller ID presentaion feature was missing. After adding it, the problem was solved.
Note: I tried all the fixes that people stated on the forum and none of them worked.