After I had rebuilt our Exchange server, I had this problem as well, accompanied with new users not showing up on the client side in the GAL (no OAB was there). It turned out that the default OAB did not have a replication set up with the server it was on. If you right click the Public folder instance and chose Folder properties, you can set it in there. After I corrected this problem, I got a 9116 event to show that it started.
From a newsgroup post: "I had to resort to calling Microsoft Support Services. It turns out that for some unknown reason after the install was completed, the Schedule system folder disappeared off the main server. After about an hour, the tech helped me redirect my system folder and now the OAB and a couple other items that were not working work great".