For what it's worth, I had the avatar long before I beat Odin in Einherjar, so I don't think that's a requirement (unless it's changed in the last few years.
Make sure that you've completely finished the ToAU storyline as Drayco said (Eternal Mercenary).
Finally, what are the chances that you've already gotten the CS and just don't remember? You can always try taking the next step (talking Yoyoroon in Nashmau as anything other than BLU) and see what happens.