We are currently having trouble setting up our new Modded Server because we are getting this Error: http://puu.sh/49Pgb.txt
We have looked threw all the Mods and checked for MP or SP only Mods and everything seems to be correct.
Does anybody know that Error?

You obviously haven't checked the readme of this repository. NoSuchMethodErrors are usually due to other mods having outdated versions of the Buildcraft API.

Start by removing all mods from the mods directory. Then add in Buildcraft. Check if it starts up properly (it most likely will).
Then add in the rest of the mods one by one and test until you get the error. There you have it :) go bug that mod's author to update the BC api.

Thank you. :)
I'm going to try it out. But it's wierd because it's just on our Linux Server O.o
It's working in SP and on a Windows Server on my PC...

Yes, this is most likely an API issue. The reason it behaves differently is because mods may load in different order on different operating systems so the mod that java pickes to be used as the "master" could be the outdated one on one OS but not another.