Previous fault-tolerant time synchronization protocols are vulnerable to the number of misbehaved nodes in a sensor network. With the increasing number of faulty sensor nodes, more erroneous data are exchanged, so it becomes more difficult to synchronize time accurately for all working nodes. This paper develops a fault diagnosis mechanism for time synchronization, called Partitioned Sample Time Diagnosis (PSTD), that can locate potential misbehaved sensor nodes and then exclude them from future rounds of synchronization. Due to the diagnosis capability, PSTD avoids interference of the identified faulty nodes and thus achieves better performance. The simulation results reveal that PSTD algorithms maintain longer time interval for the time-synchronized network compared to the previous protocols.