i have the same issue with my BB8310 and a collegue with BB8800. We both updated from 4.2 OS to 4.5. I also tried removing / reinstall the BB Messanger.
This don't worked for me
I read in another forum that it would help to wipe the device completely.... I will try this when i got my BB9000
Hopefully there the issue will be solved.