Okay I found out his issue and walked him thru the solution. As it turns out his Work has WIFI for all the different techs that come in that need access to the internet for work stuff, but as it turns out it is HEAVILY tied down, and blocks all sorts of ports.
So as a test I shut off my cellular data and connected to the WIFI and I experienced the same issue. I turned off WIFI and Cellular data back on, restarted the APP Store and Voila! I was able to download apps again. So it is a port blocking issue.
I went a step further tho and connected my Ipad to the Wifi and I was able to download and redownload App's I purchased already so I wonder why it didn't effect the Ipad like it did the Iphone.
Either way problem solved.