Hold that thought. what I previously posted was incorrect. But I have discovered how to speed it up;
These machine are part of a Samba Domain - if I log in as a local account - these issues go away - if I log in on a domain account these issues plague these machines.
Does anyone know where I should poke next?
Well - this took a while to fix, but it reared it's ugly head in another guise where another member of the domain couldn't create a profile in outlook 2013.
The fix is as follows;
Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Cryptography\Protect\Providers\df9d8cd0-1501-11d1-8c7a-00c04fc297eb]
"ProtectionPolicy"=dword:00000001
Yes, just one key.
Quote