|You can't install Windows on a logical partition. |
Actually you can. This then becomes the boot partition,
What has to go onto a primary partition is the boot files, NTLDR, Ntdetect.com and boot.ini. This then becomes the system partition,
When you deleted the primary partition all the boot files went with it. I don't think you can convert a logical partition into a primary partition so you need to create another primary partition.
What you might try is once you have a primary partition boot from your Windows CD and go into the recovery console and type FixBoot. The boot files may well be copied and a correct boot.ini file created to allow you to boot the exiting Windows installation.
There are plenty of partitions managers that will recover deleted partitions from outside Windows. In fact you a restricted as to what you can do with partitions from within Windows as Windows tries to protect itself.
Test Disk is one to try.