App Store has been down for update check on my phone AND from itunes since yesterday (thurs 9/4). But I have still been able to install new apps directly from my phone.
i had the problem with itunes update not available, only on the updates page on the iphone (never tried itunes on the computer) but when i went to download an app, i got an error message (can't remember what it said). so i logged into itunes store and checked my account info. turned out that my credit card had expired. fixed that and it fixed the updates problem