Configuring SharePoint 2013 Apps is kind of a pain in the A: In addition to all of the DNS work that needs to be done (FYI: usually the SharePoint guy has no permission to change DNS, and in most organizations changing DNS in ANY way requires approval from someone who ranks Jesus level or higher), but then there is all of the supporting services, service apps, and service app proxies. Not to mention the shell Web Application, the certificate procurement and configuration if you are using SSL, etc.
A Google search will get you the basic list of these services that need to be running:
1. App Management Service
2. Microsoft SharePoint Foundation Subscription Settings Service
3. App Management Service Application & Proxy
4. Microsoft SharePoint Foundation Subscription Settings Service Application & Proxy
So you are done, right? DNS - check. Shell Web Application - check. Certificate configuration - check. Services & Service Apps - check-to-all.
But then you head in to Configure App URLs, and you are hit with this:
"The Subscription Settings service and corresponding application and proxy needs to be running in order to make changes to these settings."
So you check and re-check that things are running. And they are.
So what to do? Oh - I know, you probably forgot the super secret additional thing that needs to be running that SharePoint is not telling you about:
Ensure the Security Token Service app pool is running.
For me, the STS app pool was running on the WFE's, but the app server where the services were running had the app pool stopped. All was working fine - no idea why the app pool was stopped - but I guess it was too much to ask that the ACTUAL problem is reported back to me rather than reporting something that was completely false. But I guess it would not be called SharePoint if it didn't try to waste your time...