I'm with Brian on this one, the sylink logs are the way forward to determine exactly what's going on.
That said, I'm going to take a stab in the dark and suggest that either the throttling options have either been set so low that the GUP is unable to cache the defs before new ones become available...
...like this article, but just setting the throttling option elsewhere:
http://www.symantec.com/docs/TECH169750
...Or, you've blocked the download of full defs to clients as discussed in the below thread:
https://www-secure.symantec.com/connect/forums/sep12ru6-full-definitions-prevent-setting-console
Clearly, these stabs of mine assume the clients failing to update are all after the full defs (as opposed to the deltas). In which case you could manuualy update them (instructions in the link below) to resolve the issue.
http://www.symantec.com/docs/TECH102606
Since you've now upgraded your SEPM to 12.1RU6, it should be storing defs for many more older revisions than before, and will hopefully avoid this issue popping up again.
#EDIT#
Oh yeah, assuming it is the throttling settings that are causing the issue, the setting up a new GUP in the remote office in addition to the existing one is unlikely to resolve the problem (unless it turns out the existing GUP is out of disk space and cannot cache the full defs).