So I've got to the bottom of this, partly I think this was my fault. I'll put solutions to each issue I encountered below in case it helps anyone else.
Unable to load the specified metadata resource issue
This was caused by me setting the 'Metadata Artifact Processing' setting on the edmx model from "EntityDeploy" to "Embedded Resouce".
So this meant it just embedded the whole edmx file file into the dll and didn't generate the ssdl, msl and csdl files instead.
I guess you have to set this to EntityDeploy for this to work and generate these files correctly. Makes perfect sense and our bad over here.
Unable to resolve assembly 'DllName.dll'
This was resolved by Andrew in the comments above, thanks for the pointer on that.
Could not find the Conceptual Schema node to embed as a resource for input file
The key to this whole issue really is this, our build server is currently on Windows 2003, so can't have .NET 4.5 installed, locally we were using EF 6.1 running under .NET 4.0 on VS2013.
However for some reason it looks like we need to have .NET 4.5 installed on our build server to get this to build even though we're not using any of the 4.5 features and targetting the .NET 4 framework.
Downgrading to EF to 4.3 solved this issue for us in the short term. Not ideal but it worked.