This sounds like a problem that you can get the best assistance from the OSIsoft Techsupport team. You can contact them to troubleshoot this problem =)
Just my personal opinion, I would check the message log at the time when you attempt to start the scheduler service to see if there is any errors logged.
Yes, checking the PI message log is definately the way to go - Notifications will give the reason it doesn't start.
An easy way to do this is to open a command prompt, navigate to PIPC\adm. Then run "pigetmsg -f" which will connect to the message subsystem and print new messages to the console as they are written. Once this is connected, start PI Notifications (can be done with net start or from services.msc). Once you get the error messages, it will probably be obvious what the problem is. If not - post back on this thread.