Hey Phil,
Do you use roaming profiles at all? We also had this issue and resolved it with a registry key and making sure we had 'Wait for Network at logon' enabled.
HKCU\Software\Microsoft\Windows\CurrentVersion\Explorer
SpecialRoamingOverrideAllowed
REG_DWORD - Decimal
1
Let me know how you get on!