HTC Desire: Recovery Mode just shows 'Broken Phone' symbol
From what I know (and by no means am I an expert on rooting) the phone with the red triangle is the standard HTC recovery mode, not the Clockworkmod recovery. So my guess is that your rooting method is not working correctly.

So, what method are you using and is your desire branded / locked to a network?

When I rooted my desire a few weeks back, I struggled to get Clockworkmod installed - I was using the Unrevoked method. I ended up having to factory reset the device to be able to install it, which is always an option, but you will lose all your saved date (I'm having to replay all the Angry Birds levels).