All of the tutorials in the tut section of Simply Maya will work for both 4.0 and 4.5 I believe. 4.5 has something called fluid effects, however, that 4.0 does not. I have not found any tutorials on the net about this particular thing, though.

What exactly would you like to learn? Modeling, textures, lighting, rendering? If you're completely new to Maya, experiment a little with the program, read some of the threads in the forums, and ask questions about stuff you don't understand. As said before, the tut section is a good place to start after you have mastered the basics such as moving around, scaling, and manipulating objects.