As soon as you select a battle stage in Vs Mode, press and hold one of the shoulder buttons(R1,R2,L1,L2) before the battle stage loads. This will randomly select new battle music.