Sharing the logs from the failed / cancelled job will help as quebek stated... Share all the jobs relating to the catalog as there should be 3 or 4 of them...
What is the catalog size ?
You say the issue has been like this for a few weeks, prior to that when was the last FULL backup? Have you been doing INCR backups too?
What are you backing up to? (disk / tape), if Disk is it sharing the same underlying volume as the catalog? is there sufficient space? (I don't think space would be the issue as that would result in ERRORs not long running jobs..)
Is the catalog being a backed up to a device connected to the master, or to a media server?
Is it on its first attempt, or has it had multiple attempts? Long running jobs may not be long running, it may have failed and retried....
Are other backups running "normally" or slow?
Has anything changed in the environment that co-insides with this issue starting? Adding of more clients, changing of retention levels, putting images on "hold", changes to policies, or storage units?
Check the filesystem usage for the catalog, the staging area for the NBDB, and disk used for backup (if using disk) this can be viewed with "df -k", if there are filesystems over 85% utilised you can start to get performance issues.
check the CPU and memory consumption and swap space usage while the backup job is running.
if backing up to a media server, check network connectivity too.
Has anyone done any changes to files or folders outside of NetBackup, such as relocating all / some of the catalog and using symbolic links?