Veritas position on licencing VMware is this (from version 5.1):

<<
MULTIPLE DOMAIN OR VIRTUAL MACHINE SYSTEMS 

NetBackup components (servers, clients, and database agents) for UNIX, 
Windows, NetWare, and Linux are each licensed
once per physical machine. If a physical machine runs multiple Operating 
Systems and Databases, then the physical machine
requires one NetBackup component for each Operating System and Database 
type. Please note that this policy supersedes
previous licensing policies that were communicated before the date of this 
document.

Exception: NetBackup Clients installed on IBM zSeries (OS/390) should be 
licensed once per virtual machine. This is an
exception to the standard NetBackup policy of licensing clients once per 
physical machine.
>>

So if you backup the underlying Linux server (e.g. ESX server), you would 
need an appropriate client or media server licence (though I'm not sure 
that anything other than a client is supported on ESX).

If you run Windows VMs on that ESX server, you also need one Windows 
client licence, regardless how many Windows VMs are on the ESX server.

If you run Linux VMs on the ESX server, you don't need another licence, 
assuming you bought one for backing up the ESX server.

We don't actually backup the ESX server and the image files - we just 
backup the VMs as if they were real servers, using the client licences. To 
restore, we would create a new VM and overwrite it from the backup.

William D L Brown