I recently changed my ROM, and as soon as done, started having lots of problems installing apps:
* the play store on my computer would report applications not available for my device, even though I had downloaded and installed them before
* the search in the phone play store application could not find those apps, and when given a direct link would show them as incompatible
* modded version of vending.apk failed to download with the following error: "app name" could not be downloaded due to an error. (942)
* trying to install the backed up apk manually gave me the error "Application not installed"
* restoring titanium backup failed and left the restore process hanging
* manually copying the apk to /system/app/ and fixing the permissions still did not show the app
I tried many things, different roms, different ril, different mods of Vending.apk and GoogleServicesFramework.apk, clearing data and cache, deleting files in .android_secure, etc, nothing worked. Searching the forum brought up many posts about other people with the same problem, but no working solution.
Finally, I found the solution: I was using the wrong gapps package!
The one I had flashed was for 2.3.2, my previous rom, whereas the new one was based on 2.3.7. It did not occur to me, that there could be enough changes to break market functionality, since I was sticking to gingerbread.
If you have the same problem, head to http://goo.im/gapps and pay close attention to the table matching the right google apps package to your android version. Download it, and flash through recovery.