Временная диаграмма действительно здесь не очень клеится. А вот диаграмма активностей именно для этого и применяется.
Странно, что Вашему заказчику не НРАВИТСЯ описание сценариев - возможно, вы их плохо подготовили?
В таких ситуация помогут комиксы - или раскадровки. Опишите каждый сценарий в виде раскадровки, дайте прототип.
Не думаю что тут какие-то диаграммы помогут:)