Neither Icon clicking nor the hotkeys are enabling proportional editing for me. I get no radius circle cursor (it stays a crosshair) and no falloff on the edits, it always acts as if it’s off.
Any ideas why this might be the case? The mesh I’m working on has a Mirror and a Subsurf Modifier added, but those are the only things remotely “unusual” about it.
Append the mesh into new file and try there. If it works, then append anything else and continue.
Not sure exactly how, but the Prop edit tool seems to have fixed itself, after trying your suggestion, Myn (thanks!) and reopening the problem file. It may not have been all that broken to begin with.
One thing I’ve noticed (and this probably contributed most to the original issue) is that the default influence radius circle is apparently very small, less than one unit diameter (?). So if you’re working in a real-life scale like I am (1BU = 1cm), you may not even see it when it’s first enabled.
It also seems that the radius circle can be hidden by other geometry in the scene, making it even harder to see.
Compounding all the other probs, changing the circle radius requires Alt+MW on my system, contrary to what the manual states (MW alone), so again, getting it to work right was a matter of trial and (more than a little) error.
Great tool once it can be persuaded 
to work!
You should also be able to use PageUp/Down. Not sure if it works on all OS’s.
%<
I don’t know what causes it, but .blend files get corrupted too often. I had a problem once, when I rendered a scene it was very dark and nothing helped it. Actually, some pixel in output image had negative RGB values, although no composite nodes or negative lights were used. Appending everything into new file solved the problem. Also there was some other rendering related problem solved by reappending entire file. And finally this one. Strange…