In effect, the DNS was setup with a domain of SP13TDevApps.com (and tested on the AD/DNS system) but when trying to add an App it returned "The page can't be displayed" even though the nasty URL (thanks MS) is indeed correct:
Everything was checked from both the DNS server and the server hosting SharePoint but nothing seemed wrong:
As a last thought, a ping on the server itself revealed that it was (as is generally normal) returning the IPV6 address:
Just as a guess, I tried adding SharePoint Server name and IPV4 address to the Hosts file on the server:
Again, this is just the environment I was in and it is development as well so take the above with a grain of salt - however, it's a pretty painless thing to try if you come across this issue but remember, if it doesn't work, remove whatever you changed and check your settings again.