I'm telling you guys. Its the way the networks were setup many many years ago. They considered internet usage a rarity, so gave it priority, however now that internet can be constantly connected its causing your calls to be rejected.
I had this problem on o2, and following some research and confirming with Vodafone that they prioritise voice traffic, I moved to Vodafone and haven't had a call rejected since. This I can 100% confirm.
The only thing I still don't understand is why I only started having this problem when I got my DHD, though I have heard rumours of the same effecting iPhone.