This code worked to remove a \n escape sequence from a string, maybe you can alter the code to work for a \u
x = somestringwithanescapesequence"
x = repr(x)
x = x.replace(r'\n', "")
The intermittent problem I was having with unicode was occurring only in modelbuilder. The problem path strings there are created by the system and the error would occur while the Calculate Value tool was reading the string -- so there was no place to work around it in code.
It was a very intermittent problem, fixed by resetting my HKCU registry hive, so I'm very happy that the ESRI support folks were able to reproduce it.
I have posted the details on resetting your user profile, including the HKCU registry stuff, here:
Resetting your ArcGIS application profile
If you continue to have trouble, I highly recommend contacting Esri support; they can walk you through this and help you solve your problem if the basic reset I describe above does not help.