For all other users they received the following message:
"The User Profile Service service failed the logon"
Microsoft do have a KB on this issue (http://support.microsoft.com/kb/947215), however in my scenario the user profile didn't exist so the fixes did not apply.
Having looked at the logs it became apparent that files within the C:\Users\Default directories had altered security permissions following the Windows updates.
As a work around I added the following command line task to reset permissions to default on the C:\Users\Default directory.
Command : icacls C:\Users\Default\* /reset