Probably you didn't add the service server to the AppManifest.xml endpoints section.
<RemoteEndpoints>
<RemoteEndpoint Url=" http://services.odata.org" />
</RemoteEndpoints>
UPDATE 1: I can't test the MSDN example today, but I was succeded in calling to an external WebService from JS Code in my SharePoint-hosted app. This app works well in production for about half a year. I will try to show here a piece of code which works for me tomorrow.
For a while you can try to troubleshoot it using Fiddler to understand what happens behind the scenes. Probably, it will get you some ideas.