The issue appears to be related to MSDE. Please ensure that user connections is set to "0". Perform the following steps:
---Go to the Command Prompt.
---Change directories to C:\Program Files\Microsoft SQL Server\80\Tools\Bin Folder on the media server.
---Run the command: osql -S%computername%\bkupexec -E -Q sp_configure
Check that the "user connections" is set to 0, which is unlimited.
If above does not resolve the issue, please reapply the MSDE2000 SP3a. You may download the same from the Microsoft website.
NOTE : If we do not receive your reply within two business days, this post would be marked assumed answered and would be moved to the answered questions pool.