UGH.  I went through tons of this headaches back on Battlefield 2 with Punkbuster, and now it appears to have come up again on BF3.  I had been playing along for months without a single issue, but then re-installed recently when I reconfigured my machine. Then I started getting this dreaded message:

Game disconnected: you were kicked by PunkBuster. Stated reason: PunkBuster kicked player  (for 0 minutes) … RESTRICTION: Service Communication Failure: PnkBstrA.exe

The forums are full of people with this same issue.  Here are some solutions that pertained to my particular problem:

1. Punkbuster didn’t even get installed.  You need to go to Punkbuster’s website, download the installer, and install it yourself.  Go here and follow the directions:
   http://www.evenbalance.com/index.php?page=dl-bf3.php
2. Punkbuster isn’t getting updated automatically.  There are HTML ‘key’ files that need to be installed and updated regularly.   You need to select 7 different links and save them in the correct folders.
   1. The first is: pbsec.htm, it goes in C:\Program Files (x86)\Origin Games\Battlefield 3\.  Be careful!  When I first saved it from the link, it saved it as pbsec-1.html – that doesn’t work.
   2. Update the remaining 6 htm files like ‘PB Client v2.317 for Win32’ et al. go into C:\Program Files (x86)\Origin Games\Battlefield 3\pb\htm
3. pbsvc.exe is missing(!).  One post mentioned that you could manually run C:\Program Files (x86)\Origin Games\Battlefield 3\pbsvc.exe and it would test everything for you.  I actually found this file was missing.  However, a copy of it was there in C:\Program Files (x86)\Origin Games\Battlefield 3\__Installer\punkbuster\redist\pbsvc.exe.  I copied it to the root BF3 directory and then everything worked.

Thanks again Origin for really making PC gaming a viable environment and reminding me why consoles have eaten half your gaming lunch.