Yes, the iPad App Store app can vanish--mine disappeared after I upgraded to IOS5. I'm trying to get it back now, as can't add new apps without it, it seems. Reboot didn't work, sync didn't work, no restrictions had been set, had two icons (last two attempted downloads) saying "waiting" incessantly. The "connect to iTunes" screen remained on and unchanged even though connected to computer and iTunes seemed to proceed with sync correctly. Apps screen on iTunes was dimmed, couldn't change settings.
Right now trying RESTORE and then re-sync. Maybe that will work?