Here is the solution which worked for me. I am running a Curve 8900 on O2 in he UK.
Go to the internet email for your service provider. For example, for O2 it is BlackBerry Internet Service
Log in using your username and password
Click Send Service Books
That seemed to crack it for me - good luck