OK, if you only have tried to install once I would try a new installation but when the installation have started up, before doing anything else, I would start Disk Utility (from within the installation app/ESD/NetInstall/whatever method you are using) and erase the partition where you want to install. If you want to go all the way you could remove the partition and create a new one (in case there would be file system errors or something similar). It could be easiest to do this from an external media like an ESD or NetInstall or NetRestore.
If it continues to give you a hard time I would start to suspect a hardware problem.