Sorry, I was misreading the original post. I was thinking more along the lines of pairwise scheduling, like for certain sports, where every team in the league plays each week, and plays each team exactly once.
This is a much different problem. It sounds like something Erdos would have worked on.
I know this wont help you, but could you point me at some info regarding the problem?