Yeah, zbrush's interface looks ridiculously complicated, and I still don't know what the vast majority of stuff does. I put off learning it for ages, just because it looked to daunting. But after seeing other peoples amazing zbrush work *cough*Alchemist*cough* I decided to just give it a go, and had the basics learnt in a weekend. If you're interested, this was the training CD I used
Digital-Tutors :: ZBrush :: Introduction to ZBrush 3.
I've not really used mudbox, but I heard it was pretty easy to to pick up and start learning. I dunno, I guess it's whatever you're comfortable with, both do the same job. I should probably give it a go just to compare.