You need to forward a port. There are quite a few ports for you to forward, but 3659 is the one port that has to be forwarded, otherwise you will not be able to connect to most, if any, servers. It has to be forwarded on UDP. When I didn't have it forwarded, I had the same error as you, even in the beta, and could only connect to 1 or 2 servers if I was lucky, but couldn't stay for long. I eventually stumbled on the program Smart Port Forwarding, which you can get here.http://smart-port-forwarding.software.informer.com/. [smart-port-forwarding.software.informer.com] You can add 3659 in UDP on there, highlight it, right click, and run it whenever you want to play BF4.
Or there is one other fix. Upon trying to forward the port 3659, as well as 443 in TCP in my Netgear router, I was told it conflicted with another service. What I did to fix that was edit one of my other ports, change it to 3659 and save, and that allowed me to open that port, then whichever port I saved over, I added again. I ran a check on some website and even though it showed the port as being closed, I have been able to connect to any server I want and I no longer need the Smart Port Forwarding program, but if forwarding is still an issue for you, you can download the program and do as I said.