vawils, Refer your colleagues to the following two rules:
* 9-8 "ART. 1 . . . A replay is the act of putting the ball in play without awarding a a loss of rally/point and without a rotation for the serve. A replay may be declared when:
...c. A player unintentionally serves the ball prior to the first referee's signal to serve;"
- - - - - - and - - - - - -
* 8-2 "ART. 5 . . . A serve is illegal and the ball remains dead if the server:
...e. Deliberately serves before the first referee's signal to begin the serve; (Unsporting Conduct)"
As you can see, unless you judged the server to have done it deliberately, you made the right call.