In a typical band diagram of a half-metal, the band structures for electrons of up and down spin are different. Why is this so?
You got it reversed: it is not a half-metal properties that make band structure different but it is the band structure that gives rise to half-metal properties.
That said, the proper question would be: why band structure may be different for electrons with different spin orientation?
The answer is that electrons do not exist in vacuum and unpaired electrons with different spin interact with each other through exchange which lead to having unpaired electrons having lower energy when their spins are parallel (please, note: what 'direction' we use for 'up' and 'down' when performing this type of calculation is completely arbitrary). So, when we have a half-filled band, we may expect electrons on it to have parallel spins. In reality it is usually not the case, because exchange interactions are fairly weak.
For more details you probably should repost on Physics.SE or go for specialized literature. You need at least basic understanding of quantum mechanics to understand the details. Some insight may be obtained here.