I can personally attest to the key method working. However, it does work much better if you use two keys. You insert each key at the angle shown in James Webster's diagram, but you turn the keys 90deg from the position shown prior to inserting them so that the second key is not prevented from going very far in by the first. Then simply twist the keys around inside of the neck of the bottle as you pull and it will make the removal quite a bit easier in terms of effort. You get a second advantage from this method besides just the obvious one of having the keys angled across from each other giving a better hold inside of the cork though. That advantage is that now the keys are at a MUCH better angle to hold on to while attempting to extricate the cork and is also quite conducive to mentioned rotation of the cork as you lift without hurting your fingers from the pressure on the thin edge of the key(s.)
Another method which is fairly effective is to take a thin flexible blade such as a boning knife (or really, any thin and flexible but strong strip of material, be it metal or plastic) and work it in between the cork and the bottle. You can then use the combination of the compression of the cork from the side with the small gap letting air in as you remove the cork to release the cork from its home inside of the neck of the bottle. This will work even better with two such strips, in fact, there is a type of coke remove that uses this very principle with two such strips of spring steel.