I had this issue, and I have a Mac Mini running Lion that I just installed a week or so ago. I have a Verizon iPhone 4 (no S), running iOS 5.1.
Here is the reality that I just discovered...
Make sure the iPhone "Cellular Data" is active (it will be unless you phyiscally turn it off, like, for testing). Turn on the Personal Hotspot on the iPhone.
Connect your iPhone to your Mac via a USB cable.
Go into the Sharing on the Mac, and go to Internet Sharing. The iPhone USB will appear and from the Internet Sharing standpoint, it will actually allow you to select "from Ehternet to iPhone USB" but, it doesn't actually work.
In reality you can only share this the other way, ie, share internet from iPhone USB TO the Mac. Perhaps Apple is readying the ability share the other way via USB, but it isn't there, yet
However, as long as you have an ethernet connection and a Wi-Fi on the Mac, you can share FROM the Mac to the iPhone via Wi-Fi, essentially setting up a Computer-to-Computer connection between the Mac and the iPhone (or, in more modern terms, the Mac becomes a hotspot).
I have read that perhaps with earlier versions of OSX the USB went the otherway, but I have never gotten it to work, and I highly doubt Apple would have taken that away, as opposed to adding it.
Hope this helps.