It is established in Timothy Zahn's books (specifically The Last Command) that some droids, security droids in particular, are actually immune to restraining bolts. Han and Chewbacca figuring out how to use a restraining bolt on a prison-guard droid (the bolt needs to be placed in one exact spot on the droid for it to work, which is so precise a task that they need Luke to use the Force to place the bolt)is actually a very important plot-point in this book.
It is possible that since R2-D2 saw military service that he was given upgrades to render him at least partially-immune to restraining bolt technology. As such, if he's left alone in a room he can use nearby materials (the door-frame) to pry off a bolt, but if he's being watched his owner, or the person who owns the restraining bolt, can freeze him if he attempts to do something unauthorised, as the Jawas do to him when he attempts to follow Threepio in A New Hope.
In another of Timothy Zahn's EU novels, Heir to the Empire, Talon Karrde's smugglers seem to anticipate this loophole in restraining bolt technology by actually placing Artoo in a restraint collar rather than a restraining bolt, which physically holds him in place so that he cannot move when there is no-one else in the room to release him. This raises the question of whether Karrde's people; are smart-enough to spot the upgrades; simply suspect them, or; are merely very cautious, smart people (this is known to be true, but may not be why they used a collar instead of a bolt). The alternative theory is that removing the bolt doesn't actually require any security upgrades, but is merely something that the average droid, as jacen.garriss says above, is not intelligent or experienced enough to figure out.
I would be inclined to ret-con the military upgrade feature I mentioned above myself if I were a Star Wars writer, because it would render the very concept of restraining bolts obsolete if they were easily removed by any droid.