TTN provides the timestamp based on the timestamp in the original join request. That timestamp is not related to wall clock time so in a window of a few seconds it time synchronisation should not be an issue.
If the issues start occurring after the gateway has been running for a few hours my first suspicion is firewall issues. When the gateway is restarted the connections are fresh and the firewall will forward the packets to the gateway, after a few hours ‘connection’ time-outs will have kicked in and packets may be lost.
To debug: install tcpdump on the RPi and wait for the moment the join fails. At that point in time start tcpdump and check for traffic on port 1700. You should see both a packet to TTN and a few seconds (about 4-5) later a packet from TTN.