That usually happens when the following steps occur.
The original owner unlocked bootloader.
They put twrp on it and did a full backup including ESN
The device developed a fault so they RMA'd it.
They restored the backup from the faulty device into the new one.
The ESN is device specific and by restoring it onto a different device you end up with not being able to connect to a network.
You can check by going into the about phone menu in the settings. If it displays your imei then I don't think this is your problem.
Have you tried popping the back cover off and checking the antennae contacts
Sent from my Nexus 4 using xda app-developers app