Winning Heroic Victorys are not the only thing it seems, i won 3 battles both where Heroic but hes still a captain the poor guy. I have 4 generals and 13 provinces so its not that i have enough either. Btw the 2 battles i was sieged so i guess for those 2 it could that it does not work with sigies.