I've had this happen to me, seemingly randomly, a number of times before. You open Visual Studio and create a new SharePoint App. You go through the wizard and then hit F5 to run, deploy and debug your app. Something happens along the way though...you watch the output window and it just keeps counting time while it's trying to deploy your app. A few seconds, becomes a few minutes, which becomes several minutes, and then finally it just quits and says sorry, there was a deployment error. Now no more walking away, looking at the sky and shouting "SERENITY NOW" friends - instead, here's a tip that will hopefully help you.
When I had this happen to me (again) today, I changed the SharePoint site collection to which I was deploying the app to one I had successfully deployed before. Sure enough, it worked like a champ. Hmm, that got me to wondering. Rather than looking at the whole side loading apps feature (which you really should not try and use as a work-around), I went to the problematic site collection and just went into the appregnew.aspx page (i.e. https://yourSiteCollection/_layouts/15/appregnew.aspx). I generated a new client ID in there and registered my app, then I took that client ID and pasted it into my appmanifest.xml and web.config file. I tried deploying to that site collection again and - voila! - sure as I'm the master of my own domain, the app deployed successfully and started running.
I've heard of many other folks hitting this issue...this is nearly as frustrating as those who can take the reservation, but can't hold the reservation, so hopefully this will buy you some peace and happiness.
I had been through this utterly frustrating issue. Thanks for helping me save several hours which I could have spent trying to debug this weird issue..