So I finally figured what was causing this, although I can't figure out why.
In our Teamcity MSBuild step, we had our Working Directory set to %build.root%
. Removing this value, so that the default of the checking directory was used, appears to have stopped that error from occurring.