STK Cartridges are normally delivered with ANSI headers. NBU will not overwrite 'foreign' media types. You need to select 'ANSI' tick-box under 'Allow media overwrite' in Host Properties -> Media Server -> Media.
Also check for errors in Media Logs Report as well as bptm log on the media server.