Could be loads of things. SRP not connected, services not running, could even be good old fashioned remove the user and readd them back on or resend the service books.
Have you checked the data connection the Blackberrys? Make sure they have Capital GPRS, Capital EDGE or 3G:
First step check the connection on the numbers
Might be worth checking all the blackberry services are running in Admin tools. Check the SRP is connected and then try adding a test user on and off and reactivate them that way. Least then we can see the logs as I am guessing they don;t know when they last had an email to know which date of the logs to look at.
Once we have email working again then we can look at permissions and see why if they are still not getting PIM sync to the blackberrys. They may even have turned off wireless reconsile for Personal information on the actual devices.
Hope that helps.