We would need a lot more info about your environment in order to grasp what is going on. Here are a few questions, but there are more.
Netbackup version of your master server.
Netbackup version of your media sever.
OS of your master server.
Size of the catalog.
Do you have any logs you can share?