How are your new profiles created? From a default on the netlogon share or from the local machines default user for example? Seeing as the issue is profile related I would start looking there.