Dogdoctor, did you get the chance to power off the PS3 completely by unplugging the power cable? Win, try the same procedure. I believe the issue is caused by the Bluetooth stack getting corrupt. To reset it, the PS3 must be completely powered off, not just shut down. That means unplugging the power cable.
Romeo - Problem Solved!
I did as you asked. And guess what. It still didn't work. I unplugged the PS3 3 times for a minute each and each time I would pair a (game) controller it would work, that is until, about the 3rd or 4th turning on the PS3 the (game) controller would just go to 4 flashing lights and USB pairing would only allow the controller to work while connected. So, no matter how many times I did this (3) the end result was the same. Mind you I had the PRO disconnected all the time during this test.
How can one undo a pairing a remote or better yet restore the BT software stacking? A PS3 Restore System Defaults.
3 Seconds later I began to reenter all my prior settings for: Network, Video, Audio, BD, Music, PSN ID info, and.... I repaired my BT headset, and keyboard. What a pain. But you said that you connected the PRO after 3.1 not before....and that got me thinking.
After I did all that, came the moment of truth. I turned the PS3 off and back on with the (game) controller. Went to register a BT Remote Control. The PS3 paired without an issue. PowerOFF (IR) = Perfect shutdown of the PS3.
Holding the IR remote control I pressed the PS button = PS3 powers on, and I press X to login and it logs in seamlessly. Sweet! I turn on the (game) controller by pressing the PS button and it connects. Hallelujah, the PRO is back in business.
Moral of my Sony 3.1 FW story: Reset the BT settings of the PS3 and repair the PRO = fully functional PRO and no BT issues. Yes!