Ok so I finally solved this. The main issue had to do with the fact that I was sold single-sided memory when I should have been sold double-sided memory. Apparently, the P8P67-MPro is not able to handle the memory chips used on the single-sided boards. The crazy thing is that both the shop where I bought the memory and the Kingston site claim that this particular part number (KVR13N9S8/4) will work with my mother board. It wasn't until I wen to the Asus site that I realized that the correct 4GB memory module is KVR1333D3N9/4G. The "G" at the end being the key difference.
This was a bit of a painful experience as I spent several days trying to solve this problem. At one point, I even updated the bios and temporarily disabled my machine due to a failed update (I actually thought I had bricked my mobo!) while I tried to get the memory working. I could have avoided this all if I had actually been sold the right memory!