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:
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.