So in my case, after doing some further investigation I've managed to work around the issue. I'll try to explain a bit so that others can try a similar solution for themselves if they have the same problem.
BF4's executable connects from local port 3659 to the remote server on the internet that you're trying to connect to. In my case I have a NAT router which connects my local network with 2 computers behind it to the internet connection. When computer A sends data to an internet server on port 3659, the NAT sees this, and any return data coming from the internet server back to port 3659 gets routed to computer A. When computer B sends data to that same internet server on port 3659, the NAT has already established that return data from that internet server is going to computer A, and thus computer B gets nothing back and can't connect / play.
The solution for me was putting a setting back on in my router that randomizes the local ports that the data was being sent from. Ie, computer A sends data out from port 3659, the NAT intercepts it, changes it to a random port, say 30000, then sends that data out to the remote BF4 server. When that BF4 server sends data back, it sends it to port 30000, and thats routed to computer A on port 3659. Then when computer B tries to send data out to that same BF4 server on port 3659, again, the NAT changes that port to something random, say 40000, and when the BF4 server returns the data, it comes back to port 40000, and the NAT knows to send that data to computer B port 3659. By this method we're both able to connect with no problems.
Again in my case, I had that local port randomization disabled in my NAT because I was troubleshooting another unrelated problem, and forgot to turn it back on.
Another solution to this problem would be to simply change the local port that the BF4 executable tries to send data out on. I don't know how to do this, but it should be a simple command line argument. If you could do this, and each put your own BF4s to different local ports, you should be able to connect without having to mess with your router (if this is the problem.)
Another way to get around this is to use a program called "Smart Port Forwarding" or something similar, which basically intercepts your data that your computer is sending out on port 3659, and changes that port to something else. If your two or more computers on the same local network are all using different ports, the NAT will be able to send the data out to each computer as it returns from the internet BF4 server. You should be able to search for that program, I'm not sure if I can post an external link on this forum.
I hope this helps.
-N