After having a new TFS image set up and trying to a get a Team Build to run, I got the following strange error:
TF42046: The build service used in the build process is not reachable. This error occurs when either the build machine is off-line,the required service is not running, Team Build is not installed on the build machine, Team Build is configured for a different Team Foundation Server or the network is not available.
After some checking, everything seemed in order. I had the Team Build Service running, the firewall configured correctly etc. After I searched around a bit for possible problems together with Marcel, I noticed that inside my Team Foundation Server settings, no one was a member of the group TFS Service Accounts anymore. During setup, the account specified for the Build Server is automatically added to this group and so it should be in there. But I had run newsid.exe and think this might have caused the problem because it does some hefty SID find-replacing.
Anyway, we needed to get the service account back in the service accounts group. This can not be done via de GUI, as the buttons to do that are disabled for this group. However, team foundation server also comes with a set of tools found below the Team Foundation Server installation directory. One of those tools is TFSSecurity.exe . This tool does allow you to add the user again.
After doing that, everything was running as it should 
Also, when searching for this problem, I got exactly 1 hit in Google, on a Microsoft forum. So I thought it would be nice to inform those guys of my findings too..