Windows 7: Domain issue with error "User Profile Service Failed the Log On"

I work in a school district and we have numerous computers that give us the error message "The User Profile Service Failed the Log On". We have tried EVERY recommended fix for this. The issue for us is that the user has never logged onto the computer before. I have not found any forums for this particular issue and am looking for someone that is working in a domain that gets this error message without that user ever having logged onto the computer before. They have logged into our domain, just not the computer. Happens randomly and includes new installs.