I just got bitten by this a second time, so I figure it's time to blog about it so that I might be able to find my own notes on why this happens next time around.
If your network supports IPv6, Lion is unable to get an IPv4 DHCP lease if it's never had one before.
This has bitten me twice: once when I booted into Recovery, and a second time just now right after a completely fresh install of Lion.
In both cases, the fix was the same: I had to tell my router to disable IPv6. As soon as I did that, my machine got an IPv4 address. I was then able to re-enable IPv6 and the machine continues to work fine on IPv4 indefinitely.
Not too much of a bother in a house with only a few macs that very rarely encounter a fresh install; but I hate to think how this would play out on a corporate LAN.