Just out of curiosity because I know the new version of the Market still seems to have it's issues, which Market are you using, the one in the Google Apps, or the newer version?
Also it may be that the app is installing on your SD Card, I've had a problem before where an app would install on my SD Card and it either wouldn't show in my app drawer when I booted my phone, or it would show the default no icon and list the app name, and if I clicked it it would say application not installed. But after letting the device boot fully and giving it a few minutes it would work as normal, it just acted weird because it needed time to read the apps off the SD Card.