How to find n-1 complete matches for bipartite graphs that are related (speed-date)?
Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:
(i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.
(ii) Each symbol occurs in every row and column of the array.
(iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.
To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.