Nice question! A comment about terminology. The object you are considering is a "balanced frequency square". Frequency squares generalise Latin squares in the sense that each row and column is a permutation of the same multiset of symbols. The term "balanced" means that each symbol occurs the same number of times.

<Apolgies: Some nonsense deleted... the cost of firing off an answer on the run>

-Ian