Why does Punkbuster kick me when I join BF3 servers?

I enjoyed Battlefield 3 on Xbox, so I signed up for EA Origins and bought the PC version. However, every time I try to join an online match, Punkbuster kicks me from the game before the window even opens:

The message says "RESTRICTION: Service Communication Failure: PnkBstrA.exe". What does it mean? I've tried re-installing PunkBuster, Origin, and Battlefield 3. I'm running Windows 7 with only Steam, Silverlight, and mouse and game controller drivers. This is infuriating.

(This assumes you have installed Punkbuster, and added Battlefield 3 to its games list.)

Download PBSVC and run it. If it claims everything is okay ( = green), try running BF3 again.

If BF3 still fails to communicate with "Punkbuster Service A", then, run PBSetup.exe and check whether you have the right path to your BF3.

PBSetup creates a subfolder for the games it registers, and remembers this subfolder's path.
If you have, for any reason, relocated the BF3 install, the service won't be able to validate the game, and fail to communicate.

As Steve himself pointed out, it might also be the Windows Firewall blocking the Service.

Try updating your punkbuster specifically for BF3.

Follow the steps outlined here: http://evenbalance.com/index.php?page=pbsetup.php

Everyone says to uninstall and install the PBsetup.exe and run the pbsvc.exe. I did all that and still had the same problem of kicking me after a few minutes of play. The check ended good. I finally read what was in the pbsvc.exe window and was enlightened. I went to my services and found that pnkbstrA was running but pnkbstrB was not running. I started the service on B and haven't had the problem of getting kicked.
Hope that helps someone, as I was getting frustrated.