I talked to Veritas and they revealed this gem, seems to fix the problem:

On the aix client:
"touch /usr/openv/netbackup/dont_sort_dir"
This touch file has been known to fix backups with many small files and the 41 
status code.


>  -----Original Message-----
> From:         Simon, John  
> Sent: Thursday, October 23, 2003 1:10 PM
> To:   'veritas-bu AT mailman.eng.auburn DOT edu'
> Subject:      Backing up a filesystem with millions of small files
> 
> I am trying to backup a new AIX system that has a JFS filesystem with about 
> 1-2 millions files, most smaller then 10k. We first were trying our TSM 
> server but TSM would give out of memory errors. So since we are phasig TSM 
> out we hooked up Netbackup and tried it, it seems bpbkar just starts eating 
> resources and after a few hours is taking like 25% of the system CPU and not 
> backing up. Any suggestions on backing up filesystems with millions of small 
> files?