I remembered incorrectly. It wasn't a patch that solved the problem. For a while our domain controllers was a mix of Windows 2003 and 2008 (or 2012). As soon as all DCs where running on the same Windows version the problems disappeared.