Ian Kemp has the answer (have some points btw..), this is to simply add some meat to one of his steps.
The reason I ended up here was that dev's machines were building fine, but the build server simply wasn't pulling down the packages required (empty packages folder) and therefore the build was failing. Logging onto the build server and manually building the solution worked, however.
To fulfil the second of Ians 3 point steps (running nuget restore), you can create an MSBuild target running the exec command to run the nuget restore command, as below (in this case nuget.exe is in the .nuget folder, rather than on the path), which can then be run in a TeamCity build step (other CI available...) immediately prior to building the solution
<Target Name="BeforeBuild">
<Exec Command="..\.nuget\nuget restore ..\MySolution.sln"/>
</Target>
For the record I'd already tried the "nuget installer" runner type but this step was hanging on web projects (worked for DLL's and Windows projects)