If you erased your hard drive, you'll need to reinstll OS X 10.6 Snow Leopard to access the App store. You won't have to pay for OS X 10.7 Lion again. Did you try booting to the recovery partition by holding the command and r keys down? If that's still there, you can reinstall OS X 10.7 from there.
If you're looking to install the current iTunes, you need OS X 10.6.8 at a minimum.
If you're still trying to update OS X 10.5 Leopard, you can download the combo update from here. Download, use Disk Utility to repair permissions, apply the update, then repair permissions again. That will take you to OS X 10.5.8.