Does the android licensing work on custom Roms, too?
If yes, then what could it be that some people can't install (=> "device incompatible") my app from market?
As long as the custom rom come with the default Android market app, I don't think this has anything to do with neither Android licensing nor your app. It looks more like a fault from cyanogenmod ROM Customization, check out here for the reported problem and workaround.
My app has also got some negative feedback from cyanogenmod user complain HTTP Live Streaming doesn't work, as it turned out, a bug from cyanogenmod ROM Customization. LOL