I've not only had that since the app store went live (3+ updates and yet all up to date when checked etc).. but I also find that if I buy an app on the phone and then Sync with iTunes, the App doesn't sync across.. so I end up having to buy it again via iTunes (for free though.. it says "App already installed.. click here to download for free" or something to that effect) and then sync it BACK to the iPhone from there..
if anyone knows of a better way, please let me know 🙂