Had exactly the same problem with 10.7.5, and all I could Google was this (and the copy over at Stack Exchange), and an article in Czech
Long story short: the Czech article led me to 'pf' which led, via apple discussions, to this:
Instructions for setting it up by hand (as the lower apple config files do not exist on my system, I presume they're the 'Mobile internet config' file that couldn't be created).
I'm typing this from behind the NATWall, so it def works.
Also, something else broke it in 10.8.2: