I tried adding this edge with the knife tool to no avail, it won't add in the desired vertices. Is there any other way to add these vertices and have them connected to both edges like the ones above?
Currently knife would be good to use. For this particular case, there are some tricks to do it even faster:
Select all intersected edges, then P > Selection;
Press Space to quickly search for Knife Project tool.
Switch to Object Mode, delete the separated object (edges).
Select the n-gon face while using Face Select mode, then switch to Vertex Select mode to quickly select related elements (or simply press A to select all elements in this case);
Hit Space to search for Split by Edge tool;
Select the two vertices on that horizontal edge, then press J.
There are some addons that are aimed to split intersecting edges, such as zeffii's X ALL, nixy's Boolean 2D Union, even the powerful Sverchok can handle some situations. they all got pros and cons, however. IMHO, We really need an internal tool to perfectly handle it (something like an enhanced version of the current Split by Edge tool).