Can you erase the disk with Disk Utility? If nothing works in Internet Recovery, you can flash a Lion installer to a USB drive with another Mac—it'll go so much faster that way, too. The disk you're trying to install to also might be corrupt, or maybe the Internet Recovery image for Lion is somehow broken.