After an answer from the AppHarbor support staff, I was able to understand and solve the problem.
There werre 2 things playing together to create the build error. The first was, that restore Nuget packages on build was activated in visual studio. Rune from AppHarbor wrote, the new implementation should go into production next week (Nov 18-24) and will most likely eliminate those kind of build errors.
The second reason for the build process to actually fail in AH was, that GitTools for VS do ignore the packages folder, when you commit changes and therefor the Microsoft.Mcl.Build
packages which causes the error.
To solve this, either manually add this via bash
//enter the version which is referenced in your solution
git add packages/Microsoft.Bcl.Build.1.0.10/ -f
git commit -m "Add Microsoft.Bcl.Build NuGet package"
or just use the git client for windows and open your local repository. It will automatically propose to commit the whole packages folder.
Commit, Sync, done. Your build should now compile.