Okay have you created a partition to format? Have you tried to use Partition Magic or Acronis to format? What about trying GParted to format?
I have used GParted on several PC's and it has not failed me yet. Either that or try to get yoru hands on ERD Commander.