Looking at the PC in question (despite the same issue having happened to at least 10 of our other new PCs) all GP objects have applied except for those under "Computer Configuration Summary" -> "Component Status".

Under this section the first line reads "Group Policy Infrastructure" then the status reads "Failed", the error with it reads:

Group Policy Infrastructure failed due to the error listed below.

The specified domain either does not exist or could not be contacted. 

Note: Due to the GP Core failure, none of the other Group Policy components processed their policy. Consequently, status information for the other components is not available.

Additional information may have been logged. Review the Policy Events tab in the console or the application event log for events between 23/08/2010 11:28:39 and 23/08/2010 11:28:39.
The issue is causing GP software not to install despite the GPO's being applied this is then apparently conflicting with it and it is not being applied.

Any ideas?