So I did find a solution - it was to do with USB Debugging (yeah. Seriously)
Although this was on Nexus 7, it might work for you as well:
Go to Settings -> Storage -> Click the three dots on top right -> Select USB Computer Connectivity -> Make sure Camera (PTP) is checked.
Voila. Camera...