Do you always see the TFTP error at the same time when the phone restarts? I wouldn't think that would be related since the phone once it's registered won't need anything from the TFTP service to stay registered, the only time that message should appear is if the phone resets and is trying to download a firmware load 9-0-3S that isn't available on the TFTP server. The unregistration reason would be indicated in the call manager traces or in the event viewer - application log. In the application log look for deviceunregister or the device name of the phone that unregistered and you might be able to get a reason code, which can be decoded with this page: http://www.cisco.com/en/US/docs/voice_ip_comm/cucm/err_msgs/6_x/alarm611.htm.
Probably not what you want to hear, but with the TCP timeout happening, that is pointing to some loss of connectivity. How many phones are at the remote site? What is the bandwidth of the MPLS link? TFTP inherently isn't marked with a QOS value, so it's possible that is not being prioritized. You would have to manually define tftp in your class map over the WAN for QOS. That is one thing to look at.