You shouldn't need to FDISK and I wouldn't recommend it for a Vista install
unless all else fails.
Once Linux setup hosed your Vista setup, repair couldn't recognize your
setup, hence the warning you got. However, Vista setup should be able to
handle this. Start a new install with Vista, when it takes you to the
screen with a few install options, there should be a button for either
right of the screen. Click that and you will see options to delete
partitions, create new ones and format.
The partition map that opens will probably show the partition with the
broken install as "Unknown" or something similar but it should show
something that you can then delete, create a new partition in its place,
format and you're good to go.