Even more worrying is this message:
"Deployment optimization failed due to an invalid assembly. Rebuild your source projects and try again."Especially worrying after rebuilding several times.
A little googling for that message turns up the fact that this is also the error message displayed when trying to use the, now removed, WP8 version of the ReactiveExtensions but not a lot else. (As referenced at http://social.msdn.microsoft.com/Forums/en-US/rx/thread/ec22cacb-a996-4244-83ca-fe3b1d5ac5ff and reported http://blogs.msdn.com/b/rxteam/archive/2012/11/14/update-on-windows-phone-8-support-for-rx-v2-0.aspx.)
It turns out that this was a result of an issue caused by a workaround after moving to TFS in the cloud.
Before moving to the cloud we had a powershell script which would rename the XAP file to include the version number of the main assembly. (This is invaluable during testing when you want to know you're installing the right version.)
Unfortunately this didn't work on the server.
Plan B was to use a simple command line app to rename the XAP instead.(It seems you can run [console] apps on the build server - but presumably with very little functionality actually available.)
To ensure that the exe was in the appropriate output directory I added it the project, set it's build action to None and set it to always copy to the output directory. This was the problem. The WP8 (this problem didn't happen in the WP7 version) compiler was seeing that there was an EXE in the project and doing something different with the final XAP.
Fortunately, this was resolved by adding the EXE to the solution directory and then referring to it from there without adding it to the project. The after build event still knows where everything is and all is good.
TL;DR/Lesson: Don't include desktop EXEs in your WP8 project, even if they're not included in the XAP.
And be sure to always test on actual devices, not just the emulator. It is possible for apps to run in the emulator and not even load on an actual device.