I just went though this process to get a MacBook Pro 2011 to reinstall an OS on a blank HD. There's a bunch of great ideas with creating a boot thumb drive and changing the date in BIOS but what eventually worked (thank God!) was pretty simple. First I cleared the PRAM by booting up while holding [Command, Option, P, R] and let it reboot twice. Here's a link for this process:
Resetting your PRAM and SMC can alleviate all sorts of issues, including those related to charging and sluggishness. Here's how to do so.
www.digitaltrends.com
Next, reboot in recovery mode but go with the option to install the latest compatible OS [Option/Alt, Command, R], not the Lion that came with the Mac. I think the problem I was having, like some of you, is that the BIOS was probably upgraded at some point and the recovery tool can't install the original OS. Since you cleared the PRAM, you'll have to enter your WiFi info along with other settings like timezone when you boot into recovery mode.
Please let me know if this works for someone else.