EDIT: Here is my new central repository for all my videos
http://www.users.on.net/~symes/gamed...videotuts.html
I've used max, maya and others and blender is my favourite.
Blender (like all 3D software) does take some time to learn but there are heaps of tutorials out there.
I have a few video tuts here
http://www.rstralberg.com/blendertuts.html
And the whole list of all available are here
http://www.elysiun.com/forum/viewforum.php?f=7
and here
http://www.elysiun.com/forum/viewtopic.php?t=31669
BTW there is a native linux version of Maya 4.5 and I'm not sure about 6 that works well but is a bit outdated now.
Give Blender a go, it won't cost anything at least

as opposed to Max which is US$3500
Blender has the advantage that the community has driven its development. Give it a chance and it is well worth the time you spent.
If you want a newbie video tutorial, check out mine at
http://www.rstralberg.com/blendertuts.html - the "axe tutorial part 1"
Don;t forget to goto
www.blender.org and see what others are making with it too!