I tried Maya, but couldn't really get into it, at the time. I did, however find a good source for video tutorials -
http://www.simplymaya.com/ - you have to sign up (free) and most of the tuts are pay-to-play, but they do have some good free ones. Make sure to get the "Cartoon Dog" series to learn the basics of model building.