I would suggest just jumping in and altering photos. If there is anyway you can downgrade back to photoshop 4 it might be easier too. IMO there really hasn't been anything to add to the program since then, all the new features after that are pretty niche.
Tools to focus on are lasso/rectangle selector thing, understanding layers, eraser, color balance, levels...then more advanced..dodge/burn tool, layer blending options, using pathes to select/delete parts of an image.
You can pretty much do anything to a photo with just those when you start combining them.
Painting is a whole other story. I have no talent with drawing so I've never bothered. Like this stuff is just mind blowing
[media]http://youtube.com/watch?v=8K_NQe57C-k[/media]