Now that I think about it, it was from that moment where I started to have doubts about him.
Would it be better to use the word "when" instead of "where," or are they both equally valid word choices? Is there any difference at all?
It should be:
It sounds a bit awkward with all those thats, but "that" is grammatically correct. It might read better this way:
Or better yet:
I'm not sure if where or when would be incorrect grammatically speaking, but either would be confusingly redundant, as they serve essentially the same purpose as the prepositional phrase from that moment -- i.e., to specify a point in time. Thus, if I hear the sentence with either when or where in the place of that, it sets an expectation that it refers to yet another point in time at which something else happened after you started to have doubts, e.g.:
In short, if you use when or where, the thought feels unfinished to this American English speaker.
That, on the other hand, serves as a conjunction introducing the subordinate clause "I started to have doubts about him." Thus, it completes a thought.