In windows2k, right click on my computer and select manage.
In the left pane of the new window, choose disk management.
This should show all partitions on each harddrive. Right click on the linux partition, format with the Filesystem of your choosing. You can also delete/add/convert partitions from here.
As far as boot loaders, I believe you can use fdisk /mbr from a Floppy to edit the boot record.