www.renderosity.com has a lot of good tutorials for most of the major (and some minor) 3D Design programs. I believe Raph.com has some as well.
Blender is great for starters, but the interface isn't what you'd call intuitive. I use Blender a lot, it's very powerful, and pretty easy once you get used to it, but that takes a bit of practice. If you go with Blender, there are good tutorials on the Blender site (and links to others). They're at
www.blender3d.org
Good luck, and happy modeling!