I had the same problem. However, updating assembly versions, copy local, and specific version settings alone did not solve my problem. In my application configuration I deploy a web and a worker role to a cloud service. After creating the service, on the configure tab I set the Operating System to Windows Server 2012 R2 to get the support for .Net Framework 4.5.1. But the error still occured.
Upon further research, I found that the *.cscfg file for my cloud service overrode the portal setting with an obscure osFamily setting of "3". When I started my project it was on MVC3 and did not yet have WebAPI and framework 4.5.1. osFamily 3 was the latest at the time.
In my latest deployment I had upgraded my site to 4.5.1 framework and MVC5. I verified it worked locally on my development machine. But it didn't work after deployment with the error referencing System.Net.Http.Formatting version 4.0.0.0 not being found. I later saw the deployment log that showed the source error
"The feature named NetFx451 that is required by the uploaded package is not available in the OS * chosen for the deployment."
Here is the blog article that led me to the solution to change the osFamily setting to 4. Then my site worked after a fresh deployment.
http://tech.trailmax.info/2014/02/azure-deployment-the-feature-named-netfx451-that-is-required-by-the-uploaded-package-is-not-available-in-the-os-chosen-for-the-deployment/