I just want to throw my hat into the ring as well as another person having this problem. I have noticed this issue today with Residence protection but I have also been working all day on trying to find a solution to this for another Bukkit mod I'm trying to use called Jobs.
Basically what is going on is that with Residence, players are able to place blocks on protected areas which is the same issue that has been reported above. With Jobs, you are able to do different tasks such as mining, digging and building to earn XP and iConomy money. Everything works with that plugin as well except for anytime a block is placed down as you are not given credit through the form of XP or money making the builder class essentially useless.
Hopefully that helps to narrow down the problem which appears to not be with blocks being placed down but with Bukkit not detecting blocks that are being placed by the player.