there is a possible solution for this... it is a simple market reset which is located in the FAQ's.... i will copy/paste the procedure for you ...
HowTo Fix market cache problem, not all apps (like Google's) can be found:
1. Open the Market (google play) and press the home button to return
2. Go to Settings \ Applications \ Manage \ Running
3. Press "Market" (google play)
4. Press "Clear cache" (do not clear data)
5. Press "Force stop"
6. Return to "Settings \ Applications \ Manage \ Running"
7. Press "Google Services Framework"
8. Press "Clear Data"
9. Press "Force Stop"
10. Start Google Market (google play), it must give an error
11. Reboot, once back Market (google play) should work, if it gives an error it could need another minute to work
12. Test the access, search Skype on the market (google play), it should return 400+ results including the original Skype and google's apps like maps / streetview / docs and skype
let us know if this solves this issue for you...thanks for your feedback