Actually, this can happen when fdisk doesn't detect your Hard Disk geometry properly. The spaces padded around the partition has happened to me, but I've never lost a partition due to that. The one time that this did happen though, it happened on my friend's computer, and the problem was a damaged MBR. In your case, it's possibly a combination of the two things.
Cheers,
cgkanchi