unexpected result with millis

I hope you didn't connected relays directly to the outputs of the board?
You shouldn't, check on :

http://todbot.com/blog/bionicarduino/

class notes 1 to 4.