Hanging License Logging Service

Our License Logging Service on our Windows 2000 Server keeps hanging at “Starting”, I assume after our full backup(using Backup Exec 8.0). If we reboot the server the service starts fine. What is causing this and how can I fix it?