I'm adding this answer to address a case which is very similar to this question. The only difference is that this question specifies a "router", while I'm talking about an 8P8C ("RJ45") connector built into a laptop. This network port does not look exactly like the picture in Linker3000's answer. The RJ45 port had a cover, which can be seen in this video: Youtube video: Connecting Ethernet cable on Lenovo laptop (@58 seconds) shows the connector, Youtube video: Connecting Ethernet cable on Lenovo laptop (@1min53sec) shows successful insertion.
I had issue with a Lenovo G51 (also known as Model 80M8). Apparently this is somewhat common with Lenovo models. Lenovo Forums show this is an issue for multiple people.
Nathan Osman's answer seems to be correct, I guess, although that word "twist" sounds a little unclear and sounds quite dangerous if you don't know what you're doing.
Related to this question: The solution was to press the clip, and then push the RJ45 cable end vertically. For this laptop, the clip needs to go on the bottom (when plugged in). So I pressed the clip (on the bottom of the connector), and then I lifted up on the clip (moving it in the direction away from the side that the clip is on). The cable came out without needing excessive force. Trying to just pull the cable away from the port, like most RJ45 connectors/ports, didn't work.
Less related to the stated question: inserting the cable was also challenging. The RJ45 port has a door, which is pressurized (maybe spring-loaded?) to be closed, so you can't just open the door and leave it open. To insert: line up the clip into the port, and then press on the clip which will press on the "door" enough to open it, and insert the clip.
Now that I spent 10 minutes exploring this issue and figured all this out, I do have some confidence that I can insert and remove cables with low risk of causing damage. Yet, I agree with the forum posters, that this is just about the most ridiculous thing I've ever seen. (I did look over the paperwork that came with the unit and found no details about this port.)