iPod touch App icons not showing up

I've recently upgraded to the 3.0 software on my ipod touch 2g. After syncing it in itunes I noticed that only 4 of my apps had been installed. Itunes didn't come up with any errors and when I accessed a couple of the missing apps in the app store on the touch the install button was greyed out and said 'installed'. They don't appear when I use the search function but a couple of the apps appear under settings (like jellycar and your reebok).

I've hard reset the ipod and haven't got anymore thoughts. Do any of you know what I could try? Thanks

I have just tried restoring it and the same thing is happening. It can't be that the apps are incompatible with 3.0 because tap tap revenge is one of the apps not showing up :s

I did jailbreak my 2.2 software and used categories. I think all of the missing apps were the ones that were hidden away in categories. I didn't think they would stay hidden after a restore.