Now that I read your message again and say that it was a format related problem it is pretty obious that it wasnt your C: drive
It is good that the drive has not been touched.
A few quick questions....
1. Does the drive now have a new drive letter?
2. Does the drive contain a new formatted drive? or when you click on it does it ask if you want to format the drive?
3. Did you try a Fast Format Recover of the physical drive? If so, did it find any files?
4. What type of search are you running now, and what file types are being returned as 1024k.
5. Do you know if the drive was originally formatted NTFS or Fat32?
This should enable me to point you in the right direction.