Camera app is missing from my Galaxy Nexus
This issue was resolved by reinstalling bigxie's 4.1.1 ROM from scratch (with a full wipe). I suspect that fiddling around with TitaniumBackup caused me to remove the system camera app, and for some reason this was not put in when I installed AOKP + gapps.

Please note! Full wipe and complete reinstall of a ROM that is missing the Camera app will not help. Therefore, choose a stock ROM or a ROM close to stock that you know include the Camera system app.

If this does not help, try reseting the phone completely to locked bootloader, unrooted stock ROM and so on as you will probably want to return it anyway if the Camera app is still gone in the stock installation :)