Updated VS2012 to VS2015 on Buiild server. Now "No TFS assemblies were found on the system" when connecting to VCS (TFS) root

We have teamCity on it's own (internal) build server, and TFS on another internal Build server.

I've just removed VS2012 from the build server and installed VS2015 on there, as all dev team have now upgraded.

TeamCity now cannot connect to TFS (which hasn't changed / moved etc as it;s on its own server) and I get the following when testing the connection to the VCS Root: 

    ERROR - No TFS assemblies were found on the system. Please make sure you have Microsoft Team Explorer 8.0, 9.0, 10.0 or 11.0 installed

I've seen various posts stating Team Explorer is required, so..

1. have installed that (seemed to use a VS2013 shell) and have connected to TFS from within there.
2. Also connected to TFS from within VS2015
3. Have rebooted

What do I need to do to resolve the error?

NB Full text of error received when testing connection

    Test connection failed in v6 :: CI - Build v6. TFS failed. ExitCode: -1
    stdout: TFS Native Verifier v7.1 Copyright (C) 2006-2012 JetBrains s.r.o.
    Running under .NET Framework 4.0.30319.42000
    ERROR - No TFS assemblies were found on the system. Please make sure you have Microsoft Team Explorer 8.0, 9.0, 10.0 or 11.0 installed

    command: C:\TeamCity\webapps\ROOT\WEB-INF\plugins\.unpacked\tfs\bin\tfs-native.exe @@c:\TeamCity\bin\..\temp\TC-TFS-20-3556_30\command.params, in file: {http://[myTFSServer:8080/tfs/DefaultCollection/, /user:***** /hash:S, C:\TeamCity\temp\TC-TFS-20-3556_29.result, ConnectionTest, $/v6/}