I'm sorry to see you guys are having this problem but I'm happy to see I'm not the only one. I was about to exchange my iPhone.
I have this trouble periodically too. It happens for awhile and then it stops. This morning the App Store on my iPhone showed I had 17 applications to update. I looked at several of them individually, and the screen for that application then showed that it was installed. I closed the App Store and returned a little bit later, and it said all were up to date, which is true. Seventeen applications is a record high number for me for this weird behavior. It has to be on Apple's end.
I can concur with the problem, however going out of the App Store and then back in seems to clear up!
Great to see I'm not alone I restored my iphone because I thought I screwed something up...
Here is the screenshot of the combined messages described above: